OPTIMAL CONTROL OF OVERSATURATED SIGNAL SYSTEMS SOME THEORETICAL CONSIDERATIONS By PANAYOTIS GEORGE MICHALOPOULOS A DISSERTATION PRESENTED TO THE GRADUATE COUNCIL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DECREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA" 1975 ACKNOWLEDGMENTS I would like to thank my advisor, Dr. J. A. Wattleworth, for his useful suggestions, encouragement, and support, I also thank Professor K. G. Courage for his help and interest shown during the preparation of this dissertation. I would like to express my gratitude to Dr. George Stephanopoulos for his advice and counsel in the areas of this dissertation that are outside of the field of transportation engineering. Recognition is also due to Dr. J. H. Schaub ur , L. and R. S. Leavenworth for their encouragement during preparation of this work. Last, but certainly no1 1 a n c appreciation is expressed to my colleagues B. Fan an an ou and Jim Hurley for their interest and moral support in this en de a vo r an d for th e i r us e £u 1 s u g g e s t i on s . 1 1 TABLE OF CONTENTS 2 LITERATURE REVIEW 4 3. 4 4. 4 • > - 4 6 ., Page ii ACKNOWLEDGMENTS .... ABSTRACT • , v CHAPTER 1 INTRODUCTION ......... 1 i 1.1. Statement of the Problem 1.2. Scope of the Study . , 3 1.3. Organization 4 2.1. Preface .......... 6 2.2. The Existing Theories ......... 7 INTRODUCTION TO OPTIMAL CONTROL THEORY ..... 21 3.1. Preface ................ 21 3.2. Optimal Control System Design ..... 23 3.3. The Concepts of State and State Variables 26 3.4. The Performance Index ......... 29 3.5. Pontryagin's Maximum Principle 3 -? SINGLE OVERSATURATED INTERSECTION 37 4.1. Formulation of the Unconstrained Problem . . . 37 4.2. Optimal Control with State Variable Constraints 52 Solution to the Unconstrained P r ob 1 e m ................ 63 Solution to the Constrained Problem . . 66 Some Computational Aspects . . . . . . . 75 The Optimum Cycle Length .... 76 CONTROL WITH BUS PRIORITIES ....... 79 Statement of the Problem ........ 79 Development of the Control Strategy . . 81 1 1 1 TABLE OF CONTENTS - continued 90 Page CHAPTER 6 SYSTEMS OF OVERS ATURATED INTERSECTIONS 9 6,1. 6.2. 6.. 3. 6.4. Solution to the Constrained Problem 7 EXTENSIONS OF THE THEORY . . Formulation of the Unconstrained Problem .....' Optimal Control with State Variable Constraints .......... 100 Solution to the Unconstrained Problem .10 5 . . 108 7.1. Single Oversaturated Intersection 7.2. Systems of Intersections .... CONCLUSIONS AND RECOMMENDATIONS . . . . , 113 113 115 APPENDIX k APPLICATIONS OF THE THEORY . A. 1. A. 2 . A. 3, A. 4. A. 5. A. 6 . 12 2 12 2 126 Introduction ....... The Unconstrained Problem ...... The Optimal Cycle Length ........ 130 The Fixed Final Time Problem . . . . . . 133 The Constrained Problem ........ 134 Sens iti vi ty An aly s i s LIS1' OF REFERENCES BIOGRAPHICAL SKETCH ........ . 141 . 144 i v Abstract of Dissertation Presented to the Graduate Council of the University of Florida In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy OPTIMAL CONTROL OF OVERSATURATED SIGNAL SYSTEMS: SOME THEORETICAL CONSIDERATIONS by Panayotis George Michalopoulos December, 1975 Chairman: J. A. Wattleworth Major Department: Civil Engineering The timing of traffic signals is one of the major prob- lems in traffic engineering practice. While several theories have been developed for the control of undersaturated inter- sections, little theoretical work has been performed for oversaturated conditions. The objective of this research is to develop the theory for the optimal signal settings of over saturated intersections. The mathematical analysis Is based state-of-the-art of optimal control theory. The folio-. ing problems are treated assuming nonlinear time varying demands: (1) minimization of total delay of isolated over- saturated intersections, (2) minimization of total delay sub ject to queue length constraints, (3) optimum cycle length determination, (4) bus priorities at oversaturated intersec- tions, (S) minimization of the total delay of two consecutiv; oversaturated Intersections with and without npnp a u ut ntJth constraints, including the effects of turning volumes and travel time between th e intersections, ana (.5 J optimal control of a system of more than two overs aturated Inter- sections In succession. Numerical examples are presented to, demonstrate the effectiveness of the theory under different formulations. VI CHAPTER 1 INTRODUCTION i . 1 . St atement of the Problem The problems associated with vehicular traffic moving through a city network of streets are numerous. The intro- duction of freeways has changed the patterns of traffic and has somewhat relieved congestion on surface streets; but the signalized intersection continues to be a major problem. The traffic demand at signalized intersections varies throughout the day and congestion frequently occurs during the morning and afternoon peak periods due to the large numbers of people driving to or from work. During the periods of congestion, the demand exceeds the capacity of the intersection, causing queuing conditions to develop. These conditions continue until, at some point in time, demand has decreased to a level below capacity such that the queues are dissolved. When these conditions develop the intersection is called overs aturated or congested. Congestion at signalized intersections can be prevented either by building new transportation facilities or by increasing the capacity of the intersection. However, con- struction of new facilities is not always feasible in urban areas, where congestion problems are most severe, nor does it necessarily result in complete elimination of the problem. The intersection capacity can be increased by proper chan- nelization, peak period parking restrictions, prohibition of certain movements during the peak hours, installation of traffic control devices, and ether conventional traffic con- trol measures. Nonetheless, these measures have certain limi- tations, and congestion at most signalized intersections dur- ing the peak periods is unavoidable. The duration of the congested period is a function of the demand at the inter- section as 'well as its capacity. Congestion can further be relieved by proper control of the traffic signals. The timing of traffic signals is one of the major problems in traffic engineering practice. While several theories have been developed (and applied success- fully) for the control of undersaturated intersections, little theoretical work has been performed for overs aturated condi- tions. At this time, only one theory has been developed for pre timed (open loop) control of overs aturated traffic signals. However, due to its limitations and some oversimplified assump- tions, this theory cannot be applied in practice. For real- time (feedback) control, few theories have been developed; but it should be noted that none have been applied in a real system, partly because of the extensive instrumentation and computational requirements and partly because traffic engi- neers tend to avoid extensive departure from conventional methods. Furthermore, some theories are based on assumptions which are unrealistic. For those reasons, the methods presently used by traffic engineers are dependent on prac- tical considerations. There is clearly a need for a realis- tic theory to solve the problem of control of overs at urate d inte rsections . 1.2. Scope of the Study Development of a theory for optimal signal control of overs aturated intersections is the objective of this disser- tation. The mathematical analysis is based on the current state of development of optimal control theory. The problems that have been studied are formulated and solved as optimal control problems. Unlike previous theories, the assumptions and proposed solutions reflect real-world situations so that the results are directly applicable in practice. The follow- ing problems have been studied. 1 . Optimal control of an i sol ated oversaturate d inter - section with, lower bound constraints on the queue lengths . The only objective of the control is minimization of the total de 1 ay . 2 . O ptimal control with upper and lower bounds placed on the q ueue l e ngth s. Minimization of the total delay is the objective of the control, but the queues are not allowed to exceed a predetermined upper limit (to prevent blocking up- stream intersections). in this case, the resulting delay is higher and the control becomes complex, 3. Bus pr ioritie s at o vers aturated i ntersections . Mini- mization of the total passenger delay is the objective of this control. . 4 Optimal control of a system of two overs aturated intersections in success ion. This problem is not a simple extension of- the problems listed previously. The number of control variables, turning volumes, and time delays of the control that are introduced enlarge the problem considerably. That is, the control action at the downstream intersection at time t is a function of the control action taken at the up- stream intersection at time t-d where d is the travel time between the two intersections, Minimization of total "system" delay is the objective of the control with lower bounds and upper bounds on queue lengths. 5 - Optimal control of a system of more than two over- s atu rate d in te rsection s. The theory of item 4 is extended to include more than two oversaturated intersections in succes- sion. Num.eric.al examples are given to demonstrate the applica- bility and the effectiveness of the theory under different formulations. It should be emphasized that in the development of the theory, demands are assumed to be time varying as in reality. Furthermore, no particular assumptions are made concerning the patterns of the demands. The theory is also applicable for initial and final states other than zero and for cases in which the control period is prescribed. 1 . 3 . ^Kf 11 !! z at ion The existing theories are discussed in Chapter 2. Chap- ter 3 introduces the fundamental principles of optimal control theory which constitute the basis of the mathematical analyse that are performed in subsequent chapters. The solutions of the problems associated with a single intersection are devel- oped in Chapter 4. In Chapter 5, a control scheme for bus priorities is developed. Chapter 6 includes the solution of the problems associated with a system, of two overs aturated intersections ; and the theory is extended for more than two intersections in Chapter 7. A summary of major findings and suggestions for future research are given in Chapter 8. Finally, several numerical examples are given in Appendix A. CHAPTER 2 LITERATURE REVIEW 2.1. Preface Although the problem of optimizing the operation of over- saturated intersections is not new, little theoretical work for its solution has been performed. For pretimed traffic control the only theory thus far developed is that of Gazis and Potts, whereas for real-time control the most widely known works are those of Miller/' Ross et al . , ' and Longley,' The methods presently used by most traffic analysts are empiri cal in form since the theories that have been developed for unders aturated intersections are not valid for overs aturated 1 ones, and the theory of Gazis and Potts" contains certain unrealistic assumptions that make its use- questionable for real-world situations. In addition, the algorithms developed by Ross e_t al . , Longley, and Lee are semi -empirical, and as such they do not constitute true optimal control policies. Therefore, testing of these models requires use of simulation techniques. It should be emphasized that up to now, none of the theories developed has been applied in a real system. What is needed, then, is a theoretical formulation that does not rely on simulation, but actually shows why and how to optimally control overs aturated signalized intersections. Before describing a realistic optimal control procedure, a discussion of existing theories is in order. 2,2. The Existing Theories Gazis and Potts" consider an intersection serving two competing demands associated with time varying arrival rates q-j (t) and q_ 2 (t) . A sufficient condition for overs at urat ion is given by q l /s l + q 2 /s 2 > 1 " ( L/c ^ (2.2.1) where q 1? q ? = the arrival rates (vehicles per unit of time) s ]_j s 2 = the saturation flows (vehicles per unit of time) c = the cycle length (seconds) L = the total lost time per cycle (seconds). Assuming that at the beginning of ove rs aturation period there are no queues on either of the two approaches, the cumu- lative demand functions are given by T i Q-i (t) = J q^ (t)dt i = 1,2 (2.2.2) o where the time origin (zero) is the onset of overs aturation and T is the final time at which the queues are dissipated. The LLiaewj.se variation of cumulative service volume for a given approach is characterized by a saw-toothed pattern such as that shown in Figure 2.1. Assuming that this saw- toothed pattern, caused by the intermittent serving of traffic by the light, caa be represented by a straight line, the cumulative service functions G, (t) are given by Figure 2 . 1 G.(t) - / Y i (t)dt o 1,2 (2.2.3) where y- is the service rate of approach i. is defined as ihe service rate Y x (t) gi(t) i = 1,2 (2.2.4) where g- is the effective green time that is given to approach i. If the saturation flows s, and s_ of the conflicting streams arc equal, the aggregate delays are minimized when both queues are dissolved simultaneously, and this is accom- plished by a single setting of the light, so that the follow ing relationships are satisfied: QiCT) - -^i- =0 i * 1,2 ' (2.2.5) S 1 + g 2 + L a c , (2.2.6) where T is the final time at which the queues are dissolved. In the more general case, however, where saturation flows are unequal, i.e., s, > s-, the 'single setting strategy is not the only one that dissolves both queues simultaneously, nor does it constitute the control that minimizes the aggre- gate delay. In this case, the aggregate delay can be reduced by trading off some delay for the major stream, i.e., the one associated with the maximum saturation flow (s,) for smaller amounts of delay of the other stream. This is accomplished by setting upper and lower bounds on the green times for each phase. The optimal strategy which simultaneously dissolves both queues at the earliest possible time corresponds in general to a two-stage operation. During the first stage the direction associated with the highest saturation flow receives maximum green time (the second approach consequently receives minimum green). In the second stage the service rates are reversed, i.e., minimum green time is given to the first direction and maximum to the second. The switching from one extreme of the control variable (in this case green time) to another is generally referred to as "bang-bang control" In control theory. Under the assumptions that no constraints are placed on the queue lengths, that the input curves are explicit func- tions o £ time j and considering two streams only, the 10 switchover point and the earliest end of ova rs aturation period can be found. By approximating the input curves fay linear functions of time of the form Qi(t) = A. + B.t (2.2.7) the switchover point and the final time are determined by the relationships A, s +A 9 s T.1 L L JL (2.2.8) (B l S 2 + B 2 S r + S l s 2 (1 "c i) t = [(c/s.) -Q. (T)-g . T](g -g . ) _1 f 2 . 2 9^ - -X here g mnv ,g_,z_, are the upper and lower bounds of the effec- tive green time of the first approach, and T is the switchover time. The above formulas allow negative queue lengths, and must therefore be used with caution. Gazis and Potts also made an unsuccessful attempt to find the optimum cycle length, assuming linear demand curves as before. Even with the oversimplified demand function, the complexity of the problem was such that to obtain a solution, B., and B ? had to be assumed equal to zero, i.e., no input it. a 1 1 e r time ze r o . 7 Green' also attempted to find the optimum cycle length assuming linear demand curves and also that A i = A 2 ;= A (2.2 .10) B} ^ B, - B and (2.2.11) S , - S „ ~ S (? 12) 11 These assumptions are better than the previous ones but they are again unrealistic. Making the above assumptions and con- sidering two approaches, Green derived the following expres- sion for optimum cycle length sL 2 r ?R i /-, C opt = ^TB + i^TI" [BL (s-f-3 + ALCS-2B)] 1 / 2 (2.2.13J q Gazis also considered a pair of intersections of three one-way streets such as shown in Figure 2.2 and assumed that the transit time and queueing storage between intersections are negligible and that the intersections become oversaturated at approximately the same time. These assumptions, of course, oversimplify the problem because the two intersections are treated as one and thus the problem is the same as that for the single intersection. With these rather unrealistic assumptions, Gazis gives a similar policy improvement scheme as that for the single intersection. Unlike the single inter- section case, the problem is not formulated as an optimal con- trol problem. As will be shown in Chapter 6, the solution of ■ this problem is not an easy one since there are two control variables, and time delay of the control is introduced. It should be emphasized that, although the work of Gazis is a major breakthrough in this area, it has some inherent disadvantages which make it difficult to apply direct!' real-world situation. The major disadvantage of the theory is that no constraints are placed on the queue lengths. Wh< an intersection is oversaturated the problem is not only to minimize the aggregate delays of the conflicting strrw :o a I 4 1 «^1 Figure 2 . 2 q, 12 but also to restrict the queues so that they do not block upstream intersections , A second disadvantage is that in a real-world situation the cumulative demand curves are nonlinear. For the pair of intersections the basic assumptions are clearly unrealistic and thus the problem is not actually solved. Similarly, the assumptions for computation of the optimal cycle length are unrealistic . The work of Miller ' and Ross et al_. is discussed next, but it is emphasized that this theory as well as the subse- quent ones applies for real-time control systems only. Miller considers a four-way intersection with heavy traffic on the two arms 1 and 2, and assumes that at time t the signal is green on approach 1. At this time the controller can make a binary decision, i.e., to change the signals Immediately (alternative A) , or alter an extension of one unit of time 15 (alternative B) . Assuming that an extension of the present phase will simply displace all future changes by the same amount of time, the differences in delays can be approximated, The difference in total delay caused by choosing alternative A over alternative B is the sum of the three terms + 5 i .\ ^ + v j=i j * 1 ± i (2.2.14) (2.2.15) (2.2.16) where 6, = the number of extra vehicles which would pass through the junction if the current phase were extended by one time unit; k = the number of cycles required to exhaust b o th q ue ue s ; r\. = the duration of the j L " red on arm 1; £-. = the time lost in acceleration on arm 1; S-, = the average saturation flow on arm 1; and N, ,N« = the number of vehicles on arms 1 and 2, respectively, which will pass through the junction before both queues have been exhausted. A test function T is then defined which is equal to the sum of the three terms listed above. If T is positive, the extension should be granted. If T is negative, extension is not granted. Similar considerations apply for extension of the green time for two, three or more extensions before endin* the curren t plias e . 14 2 ,o Miller"'"" did not consider the interactions of adjacent intersections, and thus did not include the downstream delays in determining an optimum extension strategy. Weinberg et al. 9 pursued Miller's model further by including downstream delays and deriving equations for the prediction of total delay as a function of the extension period. Weinberg et al. also extended the theory for more than two phases. 4 Ross et al. , basing their work on a philosophy similar to that of Miller and Weinberg, developed a computer control scheme for traffic, responsive control of a critical intersec- tion that not only minimizes the total delay of all users of the intersection, but also minimizes the total delay accumu- lated at downstream intersections. This was accomplished by further simplifying Weinberg's model. According to this scheme, the cycle length of the critical intersection is allowed to vary between a maximum and a minimum value; however, the cycle lengths of the adjacent intersections were assumed constant. The turning movements were ignored and the effect of downstream residual queues upon total delay were assumed negligible. The new scheme was compared with that of fixed time control by means of simulation and was found beneficial. There are certain disadvantages associated with the above theories. The first is that when the intersection is over- saturated, a single extension of a phase does not simply dis- place ail future signal changes by one unit of time as was basically assumed by Miller 2,0 and others using the same con- cept. This may be approximately true for undersaturated 15 conditions for which Miller's model also applies, but for overs at ur ate d conditions this assumption is questionable- since the queues are not exhausted in the "next cycle" if the previous cycle is extended by n • At units of time. The other major disadvantage is that in order to apply these models, predictions of several variables are necessary. These predictions reduce the accuracy "of the estimation of the intersection "gain" T. Another disadvantage is that the effects of downstream residual queues upon total delay are not negligible as was assumed by Ross e_t al. , but should be taken into account when system delay is considered. in addition, no theory was developed for a system of overs aturated intersections . 1 According to Gazis, 'the above schemes could probably be improved by application of the familiar techniques of adaptive control suggested by Kwakernaak [11] for a single inter- section, namely, predicting for the next five periods and applying the best strategy for one period only." None of these schemes has been tested as yet in a real system, partly because of the relatively extensive instrumentation and com- putation requirements, and partly because traffic engineers tend to avoid extensive departure from conventional systems. Minimization of total delay was the objective of the con- trol theories discussed thus far. Attention is now given to theories where emphasis is given to queue lengths rather than to aggregate delays. 16 A control scheme for a two-phase congested intersect! on employing a "queue balancing" strategy was proposed by Long- ley. This strategy seeks to hold a particular linear func- tion of the intersection queues to a value of zero by adjust- ment of the green time split. This linear function is termed p the "queue unbalance" (Q.) and may be defined as Q i = <*il + ^13 " B i 2 Q i2 B i4Qx4 (2,2.17) where i denotes a particular intersection and j = 1,2,3,4 is a particular approach. The queues (Q. .) are measured at the end of the appropriate green period, and the B. . terms are weighting factors indicating the relative undesir ability of the queue on the appropriate arm; the green time split is adjusted in the succeeding cycle so as to reduce the queue i nib a 1 an ce to zero. If the total traffic flow to the junction is high, but below saturation level, this strategy will ensure that ail queues with nonzero weighting factors will gradually disperse and the green times will be proportional to the total traffic flows on opposing arms. If the traffic flow exceeds the satu- ration level, the queues will inevitably increase, but the desired balance will be maintained and the green split will again depend upon the traffic flow, This, of course, does not necessarily mean that the queues will remain below some predetermined upper limits. The control action is achieved by varying the green time for arms 1-3 which move simultane- ously in accordance with the relationship 17 n-2 g,Ci) - A. Q.Cn-lj + B j _ £ Qf (in) (2. 2. IS) ni=0 where g i (n) is the value of green time for arms 1-3 on inter- section i in excess of its equal split value during the n th traffic light cycle. The parameters A. and B. are called the proportional and integral controller gains, respectively, and their values must be selected (empirically) with care to ensure a satisfactory behavior of the signal. According to Longley, the proportional controller simply increases the green time for arms 1-3 whenever the queue balance is positive and vice versa. The integral controller seeks to ensure that no steady-state queue unbalance exists when the total traffic flows on opposing arms are themselves unb alanced. The difficulty here lies in the selection of the param- eters A 1 and B i which must be determined empirically and also in the definition of the queue which, due to the various com- putational difficulties, is relaxed to include all the traffic within a certain distance of the intersection. In addition, the queues are not measured constantly but only after the end of the green period. This makes the method inflexible, considering the fact that it is designed for real-time con- trol. Thus, the decision is made for the next cycle rather than for the present cycle as it is done with the real-time control methods mentioned previously. For the system of intersections, Longley 5 considers a perfectly symmetric network with equal input flows on all 18 arms, and an Input flow rate exactly balanced by an output, flow rate on each arm. In addition, he assumed that equal queues --at the end of the appropriate green pe riods - -exist on ail arms and the queue unbalance is therefore zero. Using these obviously unrealistic assumptions, Longley derives the f o 1 1 ow ing f o rmul as : B B n " 2 r QiCn) = -Q i (n-1) - I Q?(X) + cA (2.2.19) m=0 g . = |_ [Q^Cn-1) + I Z Q*(m)J (2.2.20) If g- L > g m # gj_ is recomputed by g i = '" S i Cg i^ g m (2.2.21) where g is the modulus of the maximum permitted green time deviation, c is the cycle length (which is assumed constant), A is the difference of the input flows between the two pairs of arms, and S. Is given by c i = S il + B I2 S i2 + B i3 S i3 + B i4 S i4 (2.2.22) Again, turning volumes are Ignored as with the single inter- se ction . T 6 Lee ?:f.. f~±.« also considered queues rather than delays as the objective of the control and developed another semi- empirical strategy called "Queue Actuated Signal Control." This is a control policy where an approach receives green automatically when the queue on that approach becomes equal to or greater than some predetermined length, regardless of 19 the conditions on the conflicting approaches. The policy- assumes that no two conflicting approaches reach the upper bound specified for them simultaneously. The assumption that the queue lengths will not reach their upper bound simultaneously- implies light overs aturation , but even in this case this possibility should not be excluded. This situation will certainly arise in case of heavy over- saturation and it is therefore necessary to establish a maxi- mum and minimum cycle length, as well as a maximum green time. This control policy is based on the concept that when queues on approach A grow to a critical length, approach A should get a green phase and keep it until the same condition arises on approach B. The placement of the detectors required for this type of operation must be determined empirically. Pig- 1? nataro et al. point out that this control policy disrupts signal coordination when the intersection is located in the midst of an area of coordinated signals. In addition, for heavy overs aturation the cycle length becomes short and this general!}- increases total delays. Making the assumption that the arrival rates are Poisson and assuming an intersection of two one-way streets, Lee . , 6 . . et ax . give approximation formulas to estimate the average d* 1 - : lys that result from this control policy. However, Pack roy suggests that when the volumes at an intersection are heavy, the arrivals are normally distributed. A critical intersection control scheme for a real-time control system is proposed in kef. 14, According to this 20 scheme, the cycle length remains constant for some predeter- mined period of time (i.e., 15 minutes) but the split changes according to the ratio Qa/(Q/\ + Q 3) on a cycle-by- cycle basis. The quantities Q^ and Q B are the critical queue lengths on the conflicting approaches measured by the detectors. Another approach to critical intersection control has been suggested by Gordon. Gordon does not attempt to mini- mize delay at the intersection but rather to maintain a con- stant ratio of the queue lengths on opposing approaches. The cycle length is assumed constant and the splits are changed according to the demand so that the ratio of the actual queues to the maximum link storage space on both phases are equal. The objective of control of all the previously discussed schemes is either to (a) minimize the total delays or (b) re- strict the queues as much as possible to prevent upstream intersection blockage. In trying to optimize the operation of a traffic signal, one would like to integrate the two objectives and develop a new control policy that both mini- mizes the delays and restricts the queue lengths at cversatu- rated intersections. This objective is accomplished in the subsequent chapters. CHAPTER 3 INTRODUCTION TO OPTIMAL CONTROL THEORY 3.1. Pre face The purpose of this chapter is to summarize the basic concepts of optimal control theory. Extensive development of the control theory is beyond the objectives of this chapter and the interested reader may turn to References 16, 17, 18 and 19 for details that are not included here. Before discussing the basic concepts of the control theory, a simple example of a typical control problem would be instructive. A commercial airliner must fly at the alti- tude and speed set by air traffic controllers. Moving the passengers to their destinations is the objective of the air- liner. At the same time, the airliner must be operated within the limits that the aircraft and passengers can safely endure. The control problem in this example is that of designing the system so as to achieve the objecti\ r es while satisfying the operational constraints. Minimum time is the objective of the control, subject to safety constraints. Some systems arc so designed that once started they oper- ate without requiring further knowledge of the process devel- opment. Such situations are examples of open loon control. pen loop control is the simplest and the cheapest form of 21 n 22 control. It generally can be applied In situations In which performance standards are not very important, or whe re the operational mode of a system is fairly stable. It is only when performance requirements are introduced that open loop control fails. However, more elaborate control schemes are costly and the engineer must carefully examine the possibility of using open loop control before proceeding to consider the feedback concept and closed loop control. In the closed loop control, the desired operating point (state) of the system is measured and compared to the actual operating point. The difference of the two (error) is fed back to the input to bring the actua desired one. Thus closed loop tal operating point to the •oritrol requires determination (measurement) of the existing operating point of the system at various times. This point is a function of the control previously applied. Since ' the operating point is sampled at various times, the terminology "s amp led- data control" or "discrete control" is frequently used. As the sampling inter- val becomes large, the control approaches open loop control. Conversely, as the interval nears zero, the control approaches continuous feedback control. The various control problems are solved by mathematical optimization techniques. The objective of these techniques is to develop .rigorous procedures for optimizing a system that can be described mathematically. The nature of some systems is such that complete mathematical description is impossible, whereas other systems can be completely described. 2 3 Several approaches can be taken to the development of mathematical methods of optimization, all of which lead to essentially equivalent results. The variational method is most widely used. This method is based on the analysis of small perturbations and therefore lies closest to the usual engineering experience. The general approach is to assume a preliminary solution and then inquire about the effect of small changes. If the solution is in fact the optimum, any change must result in poorer performance. The precise mathe- matical analysis of this fact leads to necessary conditions, or equations, which define the optimum. Similarly, the analysis of the effect of small perturbations about a non- optimal solution leads to computational procedures which pro- duce better solutions. 3 • 2 • O ptimal Control System Design Control, in the sense to be used in the following chap- ters, is concerned with affecting the physical behavior of systems. Control may be achieved by means of mechanical, electrical, electromechanical, electronic, and other devices which must function without direct human intervention or supervision . Obviously, the control of a system can be obtained in a number of ways. Usually the optimal one is sought. The need to control a system in an optimal fashion was the reason for the development of the optimal control theory and design. 2 4 Optimal control design methods utilize, as will be seen, state variables to describe the system and an index of per- formance (objective function)-. As a rule, the objective func- tion is expressed as a scalar function of the state and con- t rol vectors , i.e., t£ I = J F(x,u)dt (3.2.1) o where I is the performance index, and x and u are the state and control vectors, respectively. The only constraints imposed upon the solution are those related to the physical restrictions of the state and the con- trol vectors x and u. Furthermore, no assumptions are made as to system configuration or linearity of the control strategy By satisfying the physical constraints mentioned above, a u solution is sought, usually denoted as u . or u * , which Op L optimizes the index of performance. To solve the problem, the differential equation of the state vector x is required, i.e., x = f(x,u) (3.2.2) Depending on the nature of the problem, the state of the system at the beginning and the ending of the control period may or may not be specified. The only inconsistency that one may encounter in the above problem statement lies in the specification of the state at the end of the control period. One must make sure that the system is controllable and that the prescribed state is reachable. 25 The problem of finding the optimum control strategy- u* is,, in general, not an easy one. Only in very simple systems and for very simple I functions is it possible to obtain explicit solutions for u*. In most practical cases, one must be content with a numerical solution generated by a digital computer, which is incorporated as part of the system. One of the advantages of this numerical approach is that one is not limited to only those I functions which result in analyti- cal convenience. Optimal control methods can be applied to nonlinear and time varying systems. Furthermore, they incorporate all the advantages of the modern digital computers. That is, they leave the computational difficulties to the computer, allow- ing the designer to devote more time to analytical problems. Clearly, the objectives of the control depend on the nature of the specific problem. There are, however, some objectives in common with several optimization problems. For example, the objective of the control may be to bring the state of the system as close as possible to the zero state at a given time. This is referred to as the terminal control problem. Another objective could be to bring the state of the system to the zero state in minimum time. This is the minimum time problem. The objective of the minimum energy problem is to bring the state of the system to the zero state with mini- mum control effort. tn the pursuit problem, the objective is to bring the state of the system to a predetermined state 26 in a minimum time. The time at which the desired state is reached is called final time and it will be denoted lie re as t 3.3. Th e Concepts of State and State Variables The concept of system is fundamental to optimization theory. One can speak of a system of equations or a physical system, both of which fall under the broad meaning of the term system. Systems are governed by rules of operation; they generally receive inputs and produce outputs affected by the inputs and the rules of operation. In addition to inputs and outputs and the rules of oper- ation, the state of the system is required for complete description. In some instances, the description of the system- can only be approximated, in others the description may be exact. To illustrate the concept of state, suppose that the equations characterizing a system are known; suppose also that outputs are to be determined which depend on the inputs and/or changes in the system after a certain time x. To accurately predict the response of the system after time T, knowledge of the state of the system after time x is the addi- tional information required. ■ The state at any time t is represented by the vector x(t) with n elements x (t) , x 7 (t) , ...x n (t); one may interpret the n independent x variables as carriers of the full information about the transient states of the system. Direct control of the system is imposed by means of m control forces u, , ^ , . .,, Ujn , which are called control 27 variables. These control forces are applied by a controller, which always constitutes both the brain portion and the brute- force portion of the overall system. The controller takes proper control action based upon input or reference commands ana information obtained from sensors concerning the actual state of the system. The controller may be a human operator; the system is then manually controlled. In an automatic con- trol system a machine has replaced the man. Initially, at t = the total system state can be expressed by the n numbers x ] (0) , x 2 (0), ..., x (0). Under the influence of the m control forces and the inputs, the state of the system will change and thus the state variables are changing with time. Although the symbol x does not reveal it directly, each state variable as a rule has a very obvious p h y s i c a 1 me an in g . The evolution of the system in time can be described in terms of the changes of its state. Since these changes are usually affected by external inputs, it is convenient to represent the transformation in state by the transition SCV E(t3 S(t £ ) , ( 3.3.1) which is interpreted as: the state at time t Q is transformed into the state at time t f (t Q < t.,-) by the action of u(t) . To illustrate this idea, consider the set of ordinary differen- tia.! equations corresponding to the general continuous time fo rrn , 28 Ay 3t" x l (t ' } = f 1 U 1 ,x 2J ...,x n5 V U 2"-->V t ) d^ . 3t X 2 (t } ~ f 2 (x l » x 2 ' • • • ' x n » u l ' u 2 ' • • • » u m » t) dx n 3t = X n (t} = f 5 (x l' x 2'---' x n' U l > u 2 ' " " " ' U m » ^ (3-3.2) where the x ± and u £ are functions of time t. As mentioned earlier, the state at any time t is described by the vector x(t) and the control is exerted through the vector u(t) . In vector notation the system of Eqs. 3.3.2 can be written as x(t) = f[x(t), u(t) , t] (3.3.3) where £ is a vector with n elements f f f Associated with the set of differential equations is a corresponding set of initial conditions which is Indicated as x(t Q ) - x(t-O) = x(0) (5 ^ 4} where it is assumed for convenience that t equals zero. The solution of the differential equations f. (i = l 3 2, . . . , n) is frequently called the trajectory of x(t) which starts at xfO) and passes through n- dimensional space up to X '-"M- The actual determination of such a trajectory may or may not be simple computational matter. When f is nonlinear It is necessary to turn to numerical techniques to evaluate the trajectory. When uft) = the system is called free or unforced. If F[x(t), u(t), t] - £~[x(t), u(t)J (. 5) 29 where f does not contain t explicitly, the system is called stationary. Finally, if a system is both free and stationary it is called autonomous. 3.4. The Performance Index The term performance measure or performance index is used to denote that which is to be minimized or maximized (to be extremized) . To measure the "goodness of control" in some meaningful manner, it is necessary to introduce a criterion which speci- fies how well the system is doing. This criterion is the performance index mentioned above. In alternative terms one needs to know how close the control achieves any goal which is set up for it. Selection of the performance index is not always an easy matter. As an example, suppose that one seeks to minimize the magnitude of a system error e 5 e (t) which is a function of time and is characterized by e - q(e,u,t) t& < t < t fe (3.4.1) where t & and t fe are specified, e(t a ) is given, q = q(e,u,t) is a given real valued function of its arguments, and u i u(t) is a bounded control action which is selected to attain mini- mum error over the time period defined by t < t < t . The a — — b manner in which the magnitude of c(t) is to be minimized is act obvious. One may cl y cnoose to minimize the integral of th e absolute value of the error over the closed interval it t !• a' n 30 or he may choose to minimize the integral of the squared error; or finally he may choose to minimize some other inte- gral of a positive definite function of the system error. Without loss of generality, in an optimal control problem it is required to extromize the scalar function l[x(0), t,], called the performance index, and expressed as n l[x(0), t f ] = _E Ci x.(t f ) = c'x(t f ) (3.4.2) where c' - [c, , c .„., c ] and the c . ' s are constants. The -L Li IX J_ notation here means that I depends on the starting value x(0) and the final time t,, In some circumstances the performance index is expressed in a different manner. There are a number of interesting points which require further discussion regarding Eq, 3.4.2. Since the origin is assumed to be the desired state, it follows that the terminal control problem is considered. If c, i = l,2,..,,n are taken as 1.0, the result is an unweighted, minimization of the devia- tion of the state at time t £ : bv setting some of the c's equal to zero these states are ignored since their deviation at time t f has no effect. Finally, it is noted that only those values at time t f , when the goal is reached, are in- volved; how this final state Is reached is unimportant in the sense that the trajectory actually followed is not involved i n th e p c r f o rm an ce i n de x , Although this performance index satisfies a number of important physical considerations, It does have the short- coming that the motion from x(0) ,0 to x(t ,.) ,t, is ignored 51 Th:Ls shortcoming can be improved if the performance index is redefined as t f I C x C0) ) t f ] = / f [x(t), u(t), t]dt f 3 4 31 o J where f Q is a scalar function with the property that its integral is a positive number. In this manner the overall trajectory is involved in the minimization. It should be noted that when the f function of the sys- tem equations contains time explicitly, this time inclusion can be removed by introducing a new variable x (t) with the properties Vl (t] = X and x n +i(0) = (3.4.4) so that t can be replaced with j^. Thus the form f Q (x,u,t) is equivalent to the simpler form f Q (x,u), which may be used without loss of generality. In summary, the previous discussion suggests that when the system starts from a given state and time, x(0) and 0, the choice of u(t) automatically determines a trajectory of x(t) in x,t space. The choice of u(t) is usually subject to Upper and lcwer bound constraints (i.e., the control action is bounded). Of those trajectories, the "best" one is selected by comparing the values of the performance index. Thus, the performance index allows the selection of the optimal trajectory. 32 5.5, Pent ry agin ' s Maximum Principle In this section the maximum principle due to Pont ry agin and his collaborators ° will 'be presented, A rigorous proof of the maximum principle cannot be given without excessive mathematical development not justified here. A rigorous derivation based on geometric arguments is given by Pontrya- S in ®Ji M.- A more readable but less rigorous demonstration than Pontryagin's is given by Athans and Falb. 17 Other more simplified versions are given by Denn 10 and Coppel, 19 and the interested reader may turn to these references, to find the proofs that will not be included here. The maximum principle is applicable to both minimization and maximization problems since minimization of a function is equivalent to maximization of the same function with negative sign. Thus Pontryagin's principle can also be referred to as minimum principle if the objective is to minimize the per- formance index. It is convenient to explain the minimum principle by considering the following general control problem. Problem: Minimize the performance index tf C = U(t), t f ] - / f Q [x(t), u(t)]dt (3.5.1) o described by the n dimensional vector x(t) - f[x(t) , u(t)] (3.5.2) ' subject to the final cond'j Lions 55 g x U(t f )j - find the initial conditi i = 1,2, (s < n) (3.5.3) on x(0) = (3.5.4) The performance index is to be minimized by proper selec- tion of the control variables U][ , u £ , ... n^ . The control variables are not arbitrary but they belong to a usually closed and bounded set U called the control region or the admissible control domain. In the above problem the final time is not specified. It is then said that t c is free to l this formulation it is assumed that the functions- vary. I' L i (i _ L 5 2 » ••■> n ) as well as df./dx are continuous The solut ion proceeds by slightly reformulating the-prob lem by the introduction of the variable x Q (t) = f [x(t), u(t)] (3.5.5) ■ith zero initial condition. The system is now of dimension n+1, i.e. x n > x i > X 9 ' It is noted th; p ^2 ' ' " " ' A n ' *«» as iiuLea inai if Eq. 3. includes t explicitly, t can be removed by defining a new variable x n+1 t so that x (0) = and x , n i n + l = i (3.5.6) thus the dimension of the system Increases by n+2. To simplify the notation, the Hamiltonian formulation of classical mechanics is Introduced. he II ami 1 1 en i an fun ct i on is defined as 34 n __ H(A, x, u) = I ^(x, u) (3.5.7) where the variables \ n , X. a a arp fim r-t-i nn~ ^p +•■;«, 0' i' 2' •'■' n x u iUn( -tioiii oi Lime and they are called adjoint variables. The adjoint variables are defined as V^ = \\ H 1 V 1 - 1 ' (3.5.8) ] =0 i J From Eq. 3.5.7 one obtains ITT _ f i - x iCO i = 0,1,2,... ,n (3.5.9) and 9 H n ^ ■ 3TT = , E X j 7TTT i = 0,1,2,... , n (3.5.10) i j = u J 1 From Eqs. 3.5.8 and 3.5.10 it follows that 3H A (10 - J- d X ■ 1 i - 0,1,2,.. . ,n (5.5.11) In general, the minimum principle gives the necessary conditions for optimal solution of the problem. In fact, the principle states that if optimal solution exists, then there exists a nonzero vector T(t) satisfying Eqs. 3.5.9 and 3.5.11 In addition, the following conditions must be satisfied: 1. The optimal control u*(t) which minimizes 1 -L x (0) , tf] must minimize the Hamiltonian £ un c t ion H at e a ch t i me point. 2. If the final time tf is free, the minimum value of the Hamiltonian function H at the final time is zero. Also, A (t f ) < 0. inial trajectory furthermore, it can be shown that along the op- the Hamiltonian is a constant, i.e., II is equal to zero, not only at t f but also at any time in the interval [0, t r] . The 35 optimal solution must also satisfy the initial and the final conditions as well as the constraints placed on the control variables. In the previous formulation the values of the state vari- ables at the final time were not fixed. However, the same results apply to fixed final conditions x(t f ) . If the final state is the origin it can be shown that A n = 1.0. u Finally, it must be emphasized that In all the formula- tions to this point the final time t, is unspecified (free to vary). If t f is fixed the theory still applies with the only difference being that the constant value of H along the optimal trajectory is different from zero. If maximization of the performance index is considered, the optimal control u*(t) must maximize the Hamiltonian at each time point. Regarding the maximum value of the Hamilton- ian a few comments are in order. Frequently the maximum value is obtained by setting 3H/3u equal to zero; that is, by actu- ally differentiating the Hamiltonian with respect to u and setting the result equal to zero. In this differentiation, A and x are treated as constants. When u*(t) is Interior to any constraints, it is necessary that 3H/3u equals zero for maximum. This, however, is not true when the optimal controls are on the constraint boundary. There are a number of further important variations on the main theorem of the maximum principle. Of particular importance is the case where the state variables are con- strained over the entire trajectory. The complexity of this. 36 formulation, however, precludes presenting the details here. The interested reader may consult the references mentioned at the beginning of this section for further information on this point. CHAPTER 4 SINGLE OVERSATURATED INTERSECTION 4.1. Formulation of the Uncons tr ained Proble m At an isolated intersection serving n competing traffic streams, cars arrive at rates q. (t) (I = 1, 2, . .., n) . The arrival/rates are time varying but have a repetitive and pre- dictable pattern from day to day. The cars are discharged during the appropriate green phases; the rate of discharge during the green Interval is equal to the saturation flow as long as there is sufficient demand. When the queues dissipate the rate of discharge is equal to the arrival rate. If the demand is sufficiently low, there are no queues at the end of the green interval. The average green time per cycle is directly proportional to the average arrival rate and In- versely proportional to the saturation flow, i.e., 57- ■ — + g i = i = l,2,...,n (4.1.1) i i where g. = the effective green time c = the cycle length q^ = the average arrival rate during the cycle 5 ■ - t h e s a t u r a t i n f 1 aw . To. general, the policy followed by traffic analysts is to allocate the total available green time in proportion to the 3 7 3 8 demand so that the same degree of saturation is allowed on all conflicting streams. That is, the effective green inter- vals must be selected such that the following relationships are satisfied: *1 n 2 S cr l to l S 2«2 L n s g 20 ^ (4.1.2) According to Webster,* the above relationship approxi- mately minimizes the average delay of the users at an under- saturated intersection. Consider that the demands at the intersection increase for some time period such that the capacity is exceeded and the intersection becomes overs aturated, For simplicity it will be assumed that there are only two competing traffic streams at the intersection and that without loss of general- :Lt >' s i is greater than s 2< The intersection becomes oversatu- rated when q- L > c q l ^2 ] or — - + — — > i _ i± S l S 7 c (4.1.3) where L is the total lost time per cycle. In this case, the theories that have been developed for- unders aturated condi- tions no longer apply since they do not minimize the total i n t e r sect i on de I ay . The peak period, as defined in this dissertation, is the time period from the beginning to the ending of queuing 'con- ditions on any approach to the intersection under considera- tion, fhe objective of the control, strategy is to minimize 39 the aggregate delay of both streams during the entire peak period. In developing the theory it will be assumed that the history of traffic arrivals at the intersection during the control period is known, and that the demand is not affected by the control decisions. These assumptions are fairlv r-^i- istic and have been used, previously 20 in the setting of pre- timed signals . Problem formulation is more easily understood through examination of Figure 2.1, in which the cumulative demand and service curves are plotted versus time for one approach.* The area between these curves from time zero to time T (the end of the overs aturated period) is a measure of the total delay to the users of the particular approach. The saw- toothed pattern of the cumulative output curve is caused -by the intermittent service of traffic by the signal. The verti- cal distance between the curves represents the queue length at a given time. The horizontal ' distance , such as t -t , represents the delay of the individual vehicle that joins the queue at time t ± and is serviced at time t ? . It will now be assumed that the saw- toothed pattern of the cumulative output curve can be represented by a straight line. This assumption is justified by the fact that the addi- tional delays caused by the saw-toothed pattern are negligible in cases of heavy overs aturation. The saw-toothed pattern can also he taken into account by shifting the curve G t .0 the *The notation and the formulation of the problem in this section aie those of Gazis.8 i " lx * 40 right by an amount equal to 1/2 (red Interval). The cumula- tive input and output in a time interval from zero to t ! arc given by Q(t) = / q(t)dt r 4 x 4 , o t' G(t) = / Y (t)dt f4 , 51 Y(t) sg(t) c (4.1.6) where q(t) is the demand rate (slope of the input curve) and ,ii:ie l. y(t) is the service rate (slope of the output curve) at t: It should be noted that the rate q(t) is time varying and is independent of the control decisions. If green time is tree to vary between a maximum and a minimum value, then the slope of the service curve y(t) Is also time varying, as shown in Figure 4.1. If g^ and g^^ are the bounds placed on the effective green time, then the service rate will also have upp e r and 1 owe r b o un ds de fined as r min c - ' ClJ - Sax = — F (4.1-7) The problem .em or optimizing the performance of the traffic ignal will now be formulated as an optimal control problem. suppose that, t L is t:he end of the overs aturation period: th 2 t j i ] : '< - [ -J - (O -G : (t J IctL f.l I ;, i - 1 o J J " " Ti Q 1 ,G 1 41 Qi Ctl Q 23 g 2 nuny Q 9 (t) Figure 4. 42 S J nCS V t}_G j Ct:) = X j Ct) = qusue l£ ngth at time t (on th< j ■ approach), Eq. 4.1.8 can be rewritten as D = 2 T A f ^(t)dt / x (t)dt + / x 9 (t)d j=l o J o T / o T =; - r [x, (t)+x ? (t)]dt The queue length x (t) can be expressed as f4 1 9 ") r ^s 1 '11 I t (4.1.10) XiOO - x 1 (0) + Q i ( t )-G 1 (t) = XjCO+Qj^Ct)- where x^O) is the queue length of approach 1 at time zero and has a constant value. Differentiating with respect to time, the following is obtained: dx dt 1 « . dQ l s lSl + dt q x (t)-u (4.1.11) where dO- q 3 Ct) - j^~ and u =■ Sj_ gl /c Similarly , * 2 (t) = x 2 (0)+Q (t)-G 2 (t) = x-(0)+Q,(t)- (4.1.12' S 7§ 7&? t (4.1.13) ma dx 2 dt + q ? (t) 2 g 2 ■ q 2 Ct) - -^ (c- gl -L) q 2 (t) - s 2 (l^-) S 2 g l q?ct) - s, ci-=-) S 2Sl S l c c s s. q? (t) - s o (1 -■=•) + — i (4.1.14) 43 If g max> g min are the u PP er and lower bounds placed on the effective green time g ± , then u will also have an upper and lower bound defined as (I) u mm c ff (l). 1 mm l^niax — < u < u = L LdX c — — max c At the end of the overs aturated period (or final time) the queues on both approaches must equal zero, i.e., x i (t,) = x 7 (t,) = 2 VU 1- (4.1. IS) Since the rush period begins at time zerc ^(0) = x 2 (0) « (4.1.16) The minimization problem can row be stated using these deveT oped constraints and boundary conditions. Problem: Minimize the delay function D » / (x 1 +x 2 )dt with t, = free to vary (4.1.17) suo'iect to dx 1 dt dx ar £ 1 = q, (t) - u(t) 2 2 . - q 2 (t) - s-U-fe + ~ u(t) (4.1.18) (4.1.19) w 1 1 h t h c b o un d a r y c o n d i t i o n s x ] (0) x.. ft, ) (4.1. 20) x, (0) "2 f +■ (4.1.21 44 The function u is defined as u(t) 5 lgl (t) (4,1.22; and is an admissible control in the interval s lS W /c l s mm u - < u < s , e w c = u mm - u - l to max /c max (4.1. 25) The problem may be restated using the following trans formations. Introduce a variable x n such that •0 dx dt x, + x. (4.1.24) with initial condition x (0) - (4,1.25) and free final condition, i. ■o (V = free to vary (4.1.26) The problem now takes the following equivalent form: Problem: Minimize the delay function (or performance index) D Min D u(t) ,t ] subject to 1 J E Max F u(t) ,t. ^ (t 1 3 (4.1.27) dx, ■0 "1 + x .-, (4.1. 2 3) at q-, CO - u(t) (4.1.29) 45 cbc, s 3t~ = X 2 = ^2^ " S 2^ 1_ c^ + ~ U ^ t} (4.1.30) with boundary conditions x x C0) - x^) - (4.1.31) V°) = W = ° (4.1.32) x (°) ■ , x Q (t 1 ) - free to vary (4.1.33) and the admissible control domain 1 min - i, < „ ^ l g max "c U min < u < — c = U max (4.1.34) and from here on the equivalent maximization problem will be considered. The above is an optimal control problem in which 1. the system is the intersection. 2. minimization of the total delay is the objective Of the control. The objective function is a function of the state variables at the final time tj defined as the end of the overs aturation period. 3. x., ,x, are the state variables describing the system. 4. u is a bounded control variable. 5 - tj is an optimization variable. 6. t is the independent variable. 7 - x q is an artificial state variable. The problem can be solved by using Pont ryagin ' s maximum principle, explained in Chapter 5. The solution proceeds by introducing the Ilamiltonian function H fi = V : * X l f l + A 2 f 2 = L A i £ i C4.1 i = , ae lined as Vi (4.1.0 46 where \., i = 0,1,2 are functions of time and they are called adjoi nt variables. For the optimality of the solution the adjoint variables must satisfy the following differential equations : dA SH dt 3x dx 1 3H dt ■ - " 3x x dA ? 3H dt 3x 2 Substitution of f yields (4.1.36) (4.1.3 7) (4.1.38) f ] , f- (Eqs. 4.1.28-4.1.30) to Eq. 4.1.35 0' *1» "2 H = A Q (x 1+ x 2 ) + X 1 [q 1 (t)-u(t)] X 2 [q 2 (t) - s (l-£) ♦ ~ u(t)] 1 and Eqs . 4.1.36-4.1.38 t ake the f o 1 lowin a form : (4.1 .39) □.a, dt dA. aT dA_ at = (4. 1.40) (4.1.41) (4.1.42) Because x Q (t^ is unspecified, the adjoint variable A at th final time must satisfy the condition w 3F n ■ i J (4.1.43) ana since F = ~ x n(^ 1 J, it follows that 47 VV = - 1 (4.1.44) Integration of Eq. 4.1.40 gives ^Q(t) - k Q = constant (4.1.45) and from Eq, 4.4.44 it follows that K 1 (4,1.46) Substitution of Eq. 4.4.46 into Eqs . 4.4.41 and 4.4.42 yiel yield; d^/dt = +1 and dA 2 /dt = +1 Integrating Eqs. 4.4.47, one obtains (4.1.47) Vt) = t + k x (4.1.43; ' an d A 2 (t) - t * k 2 (4.1.49) where kj and k 2 are the constants of integration. Substitu- tion of Eqs. 4.1.44, 4.1.48 and 4.1.49 into Eq. 4.1.35 results in L. s ? H = C" 1 )Cx 1 +x 2 )+(t+k 1 )[q 1 -u] + (t+lc 2 )[q ? -s 7 (l-^)+-i u ] C s [-t-k 1 +Ct+k 2 ) i i]u-(x 1 +x 2 ) + (t+k 1 )q 1 + (t+k 2 )[q 2 -s 2 (l-|)J s 2 s - [(~-l)t+(k 2 -£- -k )]u 1 z ' ~1 L L + { ^l +c i2- s 2 (i -c )]t ^ X l +x 2 3+]c l^l +k 2^2- s 2^ 1 -c i)] (4.1. SO) 48 :his equation can be rewritten in a more simple form as H = zu + w (4.1.51) where So S 2 ,w . „ 2 Z = ( it- 1}t + (k 2 sT^V (4.1.52) '1 an d L W = {q l + c l2- s 2 a -^ t-Cx 1+ x 2 )^ iqi+ k 2 q 2 -s 2 (l-|)}(4.1.53) Pontryagin's maximum principle 16 states that for optimal solution the following conditions must be satisfied: 1. The optimal control u*(t) must maximize the Hamiltonian (Eq. 4.1.51) at each time point. 2. Since the final time at the present problem is free to vary, the value of the Hamiltonian H at the final time must equal zero. Further- more H is constant and equal to zero not only at the final time but also for the entire control interval [0, t], The optimal solution can be obtained by proper determina- tion of the control variable u so that the above conditions are satisfied. From Eq. 4.1.51 it is seen that the Hamilton- ian H is a linear function of u, therefore 3H/5u = z . • (4.1.54) In order to satisfy condition 1 as stated above, it is neces- sary to examine the sign of z which may be negative or posi- tive or, finally, it is possible that z equals zero. The optimal control u*(t) when z is greater than zero or when z is less than zero can be determined if the II versus u curv es are drawn (Figures 4.2 and 4.3). From Figure 4.2 one can s i . verity that 3H 3u v— = z < u- = u mm 49 (4.1.55) Similarly, from Figure 4.3 it is clear that 3H ^— = z > ■+ u- = u ou max (4.1.56) : uations 4.1.5b and 4.1.5 6 are the results of condit ion 1 according to which H must be maximized at each time point. However, when z equals zero conclusive results cannot be drawn by plotting the H versus u curve as before. In this case, the problem is solved by noting that z is a linear function of time. Therefore there will be at most one time point t at which z becomes zero. At this time point z chang sign, Without loss of generality it has been assumed that s 1 is greater than s 2 and the ratio s 2 /s, is less than 1. Then from Eq. 4.1.52 it is seen that the coefficient of t is negative , i.e., '2 /S l - 1) < (4.1.5 7) therefore z (t) is a straight line with negative slope, as shown in Figure 4.4. Figure 4.4 shows that in the interval L z is positive, whereas after this interval z is nega- tive. Consequently, at time t the o i.e. , F timal control is u - mm ' 3H 3u U" u mm (4.1.5 8) In summary, the preceding analysis indicates that if csli/'du is u* z is positive, the optimal control u max H 3H/3u < I/3u > f) mm max u Figure 4. slope - (-£ -1) 1 T \ L Fi sure 4 . 4 51 lf on / du - z is less than zero, the optimal control is u* = u ■ mm* 3. at the time point x at which 3H/9u = z becom t zero, the optimal control u* is switched from maximum to minimum. es The time point x at which the control variable u is switched from maximum to minimum is called switchover point, and the associated control bang-bang. The trajectory of u is shown in Figure 4.5. In traffic terms, this control implies that the effective green time g ± is maximum in the interval [0, x] and minimum in the remaining interval [x, t ]. Con- versely, since the sum of the green times is constant, g 9 is minimum in the interval [0, xl and maximum in the interval f T » t ±h Xt is important to note that the possibility that z does not change sign during the entire interval [0 , t ] should not be excluded. In this case, u* is either maximum or minimum, depending on the sign of z, for the entire inter- val [o, t 1 ]. It is clear that for the computation of the switchover time, the final time and the minimum delay knowledge of the demand curves is required. If the demand curves are linear functions of time of the form Q i = A i + V i - 1,2 (4.1.59) analytical solutions can be obtained as indicated in section 2.2. This assumption, however, implies that the arrival rates are constant and not varying with time as it happens in reality. Furthermore, in the preceding analysis, no 52 u u A u L ' max rain f L- J ^ Figure 4 . 5 consideration was given to the maximum or minimum size of the queues. Therefore the solution (even for the linear demand case) may allow the queues to become negative before the end- ing- of the overs aturation period. A queue is said to be negative on a particular approach when the light is green and there is not sufficient demand. This situation should never be allowed before the ending of the oversaturation period. In addition to the lower bound, upper bound constraints must be placed on the queues so that upstream intersections are not blocked. The theoretical considerations and the solution to this more general problem are presented in the following sections . 4.2. Op t i m al Con trol with S tate Var I a b 1 . e Cons traints In the previous analysis constraints we re only placed en the decision variable u(t) , Attention is now given to the 53 more general problem in which upper and lower bounds are placed on the state variables (queues). As mentioned earlier, the queues must always be nonnegative , otherwise green time is wasted. On the other hand, if the queues are allowed to grow with no restrictions, upstream intersections may be blocked. Consequently, congestion may spread to adjacent intersections even though the demand may be lower than the capacity there. In fact, the effectiveness of any control scheme lies in its ability to limit the queues to some desired level. This analysis will show that when both queues reach the upper bounds simultaneously, the cycle length must be free to vary. Thus, upper and lower bounds on the cycle length must be established. By considering queue length constraints, the problem is placed on a more realistic basis. The new formulation follows. Problem: Minimize the delay function Mm XQCtn) = Max F - -sq^i) = ~ f (x,+x ? )dt (4.2.1) u(t),t 1 u(t),t 1 o subject to ax, dt dt ' x + x "1 ^2 £'-, = q-jCt) -u (4.2.2) (4.2.3) dx. tit: f-7 = C], -S„ (1- — ) +-— LI I -2 2 • C S , (4.2. with in.it and final conditions S4 >^(0) - x 1 (t 1 ) - x ? (0) = x (t -> \ <• i ,' L 1 x (0) - (4.2.5) (4.2.6; (4.2.7) u is an admissible control in the interval s,g (1) ■ s od) -i|^ = u . < u < ..l g ^x = u c mm — — c max and the additional state variable constraints (4.2.8) x. a, x > x, upper bound for queue 1 upper bound for queue 2 (4.2.9) (4.2.10) (4.2.11) (4.2.12) Optimal control theory states that if the constraints s tor any time interval are strictly inequality constraints, they do not place any restriction on the variation of the optimal control. One only needs to ash what changes are required when Eqs. 4.2.9 through 4.2.12 become equality constraints for a finit e period of time. That is, the equalities present a problem when they hold for a finite period of time. However, if they hold only for one time point they pose no problem, because the control variable is not affected. Therefore, when the bounds tend to be exceeded for some time interval, Eqs, 4.2.9 through 4.2.12 become equality constraints , J - • - • 3 a l or ■ :> 1 X - Ct ~ X I 1 a ? OI S 7 = x ? -a ? - (4.2.13) (4.2.14) x, - or S- = x, -0 = x, 1 3 11 x or S. = x ? -Q x. (4.2.15) (4.2.16) To simplify the analysis, first consider only equality con- straint 4.2.15. Afterwards, extension to include the remain- ins constraints is simple. Consider an interval [t (1) A2\ ] during which the opti mal trajectory of x, lies along the constraint (see Figure 4.6), Since Eq. 4.4.13 holds as an identity, i.e., it is true independently of the value of t in the interval [t^ , f 2 1 t ], it can be differentiated with respect to time to obta: but dS. at dx- dtT dx. aT q r u (4.2.17) (4.2.18) and so q, -u = t CD <t<t (2) (4. 2.19) Therefore, Eq. 4.2.19 must be satisfied for every time in the interval [t l ~ J , t ^ J ] where the equality constraint 4.2.15 holds. In addition, it is required that (see Figure 4.6) SjttW) - , ctW ) - a - (4.2.20) That is, when Eq. 4.2.20 is valid, Eq. 4.2.19 or its corre- sponding Eq. 4.2.13 'is valid for the entire time period [t^ ■ (2) ]. Therefore, Eqs, 4.2.19 and 4.2.20 are equivalent to 4.2,13. i>0 X. t CD (2^ Figure 4.6 For a problem having equality constraints such as 4.2.19 and 4.2.20, the differential equation for the adjoint vari- able A, is given by 1 & J 2 ('. dX. i = d r x 3fj r3R x1 -1 3R X 3 x , 9 u [ 3 u J dX- X. J (4.2.21) Furthermore, at time t = t (1) :he adjoint variable X 1 should satisfy the fallowing condition: (4.2.22) and since 3S-/3X, = 1 (see Eq. 4.2.20), it follows that \ 1 (t (1) -) - A l( t^ + ) ♦ y (4.2.2 3) where A, is a constant to assure the discontinuity of the trajectory of A, in the vicinity of t' ^ (see Figure 4.7), This condition is unique if it is required that X be con- tinuous 5 7 Similar analysis applies if equality constraint 4.2.14 holds and equations such as 4.2.20 and 4.2.22 need to be derived. - . Consider an interval [t^ , t ^ J ] during which the opti mal trajectory x~ lies along the constraint 4.2.14 (see Fig- ure 4.8). Since Eq. 4.2.14 holds as an identity for every time point in the interval [t^, t *- ^ ] , it can be differen- tiated with respect to time to get dS „ dx ? a"t~ " dt = DUG dt therefore dx ? , s ? ' * q -s (l-|) +? £ u L £ C S 1 R 7 q 2 -s 2 (i-!) + Jf u = ° t (3) <t<t (4) (4.2.24) (4.2.25) (4.2.26) A, / y / ^x 1 (t (1) ") t^ Figure 4.7 58 Figure 4. Thus, Eq , 4.2,26 must be satisfied for every time point in the interval [t- , t L ; ] where the equality constraint 4.2,14 holds. In addition, it is required that S^t^) = x 2 (t^)-a. (4.2.2 7) That is when Eq. 4,2.2 7 is valid, Eq. 4,2.26 or its corre- sponding Eq. 4.2.14 is valid for- the entire time period [t^ f'4 1 t l •' ] . Therefore, Eqs . 4.2.26 and 4.2.2 7 are equivalent to Eq. 4.2.14. Because Eqs, 4.2.26 and 4.2.27 are equality constraints, the differential equation for the adjoint variable X-, is given by dX, a~t 1- - T. 3±„ 3 f . (dR^-\. -1 3 R, 3u Du "2 J ] Also, at the point t = t^ ' the adjoint variable X- must- satisfy the following condition: (4.2.2 8) 59 M' (3) (3) 3S. 3 - * 2 Ct^ ) + U 2 3-±. A ? (t^^) + u (4.2.29) rt^) where u 2 is a constant assuring the discontinuity of A ? at the vicinity of t - J . Equations 4.2.21 and 4.2.23 must be satisfied only when constraint 4.2.9 is imposed. Equations 4.2.2 8 and 4.2.29 must be satisfied only when constraint 4.2.10 is imposed. The differential equations 4.2.21 and 4.2.28 require further expansion. Equation 4.2.21 yields 2t ~TiT du [ 3u j dxl u) A f3[q- L (t)-u] 3[q 1 (t)-u] (3 (q- [ -u) ) - 1 3 (q n - u) j 3x^ ' du ~ dU h f ^c^Ctj-u] 3[q 2 ( t )-s 2 Cl-|) + ii u] 3x- 3u fH^-ujyl 3(q 1 -u)) • u [o-o(-i) " oj-A n - [o-C-D(-i)" 1 o] 1 m.i co-(~-)(-ir 1 -co)]-x 2 = ° (4.2.30) Therefore \- } (t) is constant in the time interval [t^ 1 ^, t^] Similarly, from the differential equation 4.2.2 8 it follows that 6 dA / ■ -[o-o(--i)' 1 o]a. [o-c-DC^-)" 1 o]a 1 '1 [O-(^)' (--)'" 0]A, = 1 1 " z '1 (4.2.31) Therefore A„(t) is also constant for the time interval [t (4'1 , t ] . (3) The previous analysis is also valid for the lower bound constraints 4.2.11 and 4.2.12. In fact, by inspection of Eqs. 4.2.13 and 4.2.15 it is seen that S ^ can be obtained from Eq. 4.2.13 by letting a, equal to zero. Thus, the results obtained for the upper bound constraint 4.2.9 are also appli- cable to the lower bound constraint 4.2.11. Similar conclu- sions can be drawn for the lower bound constraint 4.2.12. In summary, the preceding analysis indicates that 1. When constraints x-j_ <_ cti or xj > are imposed a. the optimal control u* is affected only when the constraints are at equality for some time interval [t(l), t(2)]. b. during this interval Ax (t) is constant and is given by Eq. 4.2.2 3. c. from Eq. 4.. 2.19 it follows that when the constraints are at equality u* = q 1 (4.2. 32) 2, When constraints x? < a? or x 9 > are imp os ed a. the optimal control u* is affected only when the constraints are at equality for some time interval [t( 3 ), tC^3j. b. during this interval A2 (t) is constant and is given by Eq. 4.2.29. c. from Eq. 4.2.26 it follows that when the constraints are at equality u ; - - [s 9 (l-~0-q,] — (4.2.33) C -L b ? 61 If two constraints are of equality simultaneously, I.e. if it is required to satisfy 4.2.9 and 4.2.10 simultaneously and the cycle length Is constant, the problem may be impos- sible. This is because In th: as e Eqs . 4.2.32 and 4.2.33 rasp trust be satisfied simultaneously, I.e., s. U" q L. 1 LS ? (l-~)-q ? ] 1 c J H 2- ! sT (4.2. 34] or, solving for c, 1 qj q 7 2 (4.2.35) • j if the given constant value of the cycle length satisfies the above relationship, a solution exists and both constraints on x ~i an -d x ? can be imposed. If not, a solution does not exist and the constraints will be violated. Equation 4.2.35 simply implies that a solution exists only if the signal is not oversaturated during the period at which both constraints are at equality. In order to circumvent this difficulty, the cycle length must be free to vary so that 4.2.35 is satisfied. In this case, a maximum and a minimum value (c and c . 1 for thp k max miru cycle length need to be established. If only x is on the equals zero or if x. equals ounda r i e tha s , 2 j: eit ner tnen considering i- x 1 ■ I !C V. b .-> ou con 62 must change correspondingly so that 4.2.36 is satisfied. Similarly, if only x« is on the boundaries, then from 4.2.35 t s 2 (L+ gl ) C sT^ (4.2.37) b 2 l 2 an-" since c, s,,, and L are assumed constant, g, must change sc hat 4.2.37 is satisfied. From 4.2.37 it is seen that if s 2 is less than or equal to q ? , a solution does not exist. This condition simply implies that the input flow rate is higher than the saturation flow at the second approach.- Conse quently, congestion cannot be avoided even by providing con- tinuous green. Therefore, it is possible to impose only one constraint and keep the cycle length constant; however, for more than one constraint, it is necessary to have variable cycle lengths. Clearly, when constraints are imposed, several switch points may exist. The number of the switch points is a function of the demand curves. It is emphasized that in the preceding analysis, no specific assumptions have been made concerning the demand. Thus, the theory is general and applicable to any demand func- tion. Furthermore, it must be noticed that control with upper bound constraints prevents upstream intersection blockage but results in higher total delay. When minimization of the total delay is the only objective of the control, upper bound constraints should not be placed. Solutions of both the unconstrained and the constrained problems are necessary at th i s po'i lit . 4.3, So l ution, to the Unco nstrained Proble m The problem of finding the optimal control u* is , in general, not an easy one. Only in very simple systems is it possible to obtain explicit solutions for u*. The situation becomes more complex when nonlinearities are introduced, and in most practical cases one must be content with a numerical solution generated by a digital computer. It is then neces- sary to develop an algorithm to calculate the switch points (if they exist), the final time and the minimum delay. In this section the minimization problem with, only lower bound constraints will be considered. When upper bound constraints are imposed, the resulting delays are higher and the control becomes more complex. This case Is treated In the next section, The algorithm for the unconstrained problem is as follows: STEP 1. Assume values for k-, and k ? The unknown integration constants k-, and k ? of Eqs 4.1.48 and 4.1.49 are needed for the computation of th e adjoint variables A, and A„. Based on the estimated values of k, and k~ an initial solution can be found. The optimal solution will be computed by Iterating on k 1 and k 2 STEP 2. Set t 1 = 0, x n (t x ) - 0, x, (t 1 ) - 0, x^ft 1 ) - an d 1 = . The initial conditions of the state variables x,,x ? , i. :he queue lengths and the total delay x„ are zero as stated iii the formulation of the problem 64 STEP 3. Put i = i+1 , t*- 1 -' - t^+At and AoCt 1 ) = -1 A^t 1 ) - t (: X (t X ) = t (l) +k. X^t 1 ) = t^ + k 1 This step performs numerical Integration of the adjoint variables (Eqs . 4.1.40 through 4.1.42). STEP 4. Find the value of z at t 1 from Eq. 4.1,52, i.e., i - c^.- Dt (i) ♦ (k 2 !i. kp. STEP 5. Examine the sign of z. If z > , ■*• u* = u ' max I £ z < , ■+ u' :; = u — ' hi in If at t'-~ - ; z > and at t K } z < 0, set t = t 1 -' ks Indicated in section 4.1, switchover point occurs when z changes sign, and the optimal value of u at each time point is determined from the sign of z. STEP 6. Determine the current state of the system. j X 1 (t Ci) );» x^t 11 " 13 ) + [ qi (t Ci) )-u*]At * ? (t (l) ) - x (t (i " 1} ) + [q 2 Ct (i) )-S 2 (l-fe + ^- u *]At x (t (i) ) = x (t (i_1) ) + [x 1 (t Ci} )+x 2 rt (l) )]At. This step performs numerical integration of the state equations 4.2.2, 4.2.3 and 4.2.4. if any of the state vari- ables are negative, steps similar to steps 2a, 5a and 6a of 65 the constrained algorithm (next section) must be followed for the calculation of the adjoint variables and the control vari- able u. STEP 7. Examine the value of H at time t ^ , i.e., f i 1 Is H(t v J ) = zu*+w = 0? If "yes" go to Step 8. It "no" put t = t +At and return to Step 3. In this step the value of the Hamiltonian function Is checked to determine whether or not it is constant and equal to zero along the entire optimal trajectory. If H Is zero at ( i "! t 1 ~\ but not at t , the assumed k ± and k ? are wrong and new values must be given. Conversely, if H Is zero for the entire interval [t^, t^], the k ± and k £ values are correct Equation 4.1.51 is used to compute H. STEP 8. Examine the state of the system at t^ 1 ^ Is x 1 (t^ 1 ^) *» and x ? (t^) = 0? , i.e.., If "no" and H(t (rj ) = o, return to Step 3 "^ ,-. 1 1 >r HCt^) j 0, put t, » t^ , no" or H(.t v J ) f 0, put t 1 = t^, total delay = x (t^ 1J ), assume new values for kw and k ? and return to Step 2, If "yes" and H(t Cl) ) - 0, END. The total delay f i 1 ( ' ~\ is x (t l J ) and the final time equals t lLJ . This step assures that the optimal values of k, and k„ i- 2 have been found and terminates the iterative procedure. If ]: l and k 2 are not the optimal, new values need to be assumed 66 and the process is repeated. The new values of k, and k ? , th however, will not be random in the 2nd, 3rd, ..., n " itera- tion, but they will be chosen by an optimization routine. The routine will minimize the objective function 7 ? I X 9 \t~ J Therefore, this step is the responsibility of the optimization subroutine. The reason for using the sum of squares of the queues at the final time in the objective function is due to 2 1 the fact that this function is quadratic. Powell has shown that such functions result in faster convergence. It should be noticed that the above algorithm ends only when the conditions of Pontryagin ' s maximum principle have been satisfied. That is, the algorithm assures that the Hamiltonian function is constant and equal to zero along the optimal trajectory; furthermore, H is maximized with respect to u at each time point. The initial and final conditions are also satisfied since the queues at the beginning and ending of the control period are zero (Steps 2 and 8). Fig- ure 4.9 illustrates the algorithm for further clarification. 4.4. Solution to the Constrained Problem In the previously developed algorithm no upper bounds are placed on the state variables x, and x- (queues). There- fore, the algorithm is not applicable for cases where minimi- zation of the total delay subject to queue length constraints is the objective of the control. Constraints can be placed cither on one or both queues; in the latter case the control' ENTER WITH: 1 » 2 ' (INITIAL VALUES) OPTIMIZATION ROUTINE K 1' K 2 .^S -Ah' x ? (t 1 ) OPTIMAL CONTROL ALGORITHM (STEPS 2-7 INCLUDED) Figure 4.9 >• K i >^7 JX-, i (optimal) -> I ->-T '1 >Tot delays is more complex because the queues may be at. the upper bound simultaneously. In the development of the algorithm, the necessary conditions for optimal solution derived in section 4.2 will be used. Since the problem of constraining one queue only is simpler, it will be considered first. In the following algorithm It is assumed that constraints are imposed only on the first queue, i.e., < x, (t) <_ a. If constraints arc Imposed only on the second queue, the algorithm still applies with some minor modifications. These modifications wil-1 also be presented. The new algorithm is as fol lows : 6 8 STEP 1, STEP 2 . Assume values for kj_ and k ? . be" - 0, Xg{t j 0, x,(t Ci] ) x ? (t^) = and i These ti\ r o steps are the sane as the ones of the previous algorithm. <J x lli t ij cl i Cb° iecK the magnitude of x. Ci) >(i) If x 1 (t^ J ) > c^ or x x (t^ J ) £ put u» q- a-, or x, = and if u . < u* < u 1 2 mm — — max go to Step 3a, Otherwise, the problem is impossib le . That is, when the constraints placed on xy are active, the optimal value of u is not determined from z but rather from Eq„ 4.2.32., If the optimal value of u lies outside of the bounds specified for u, solution does not exist because the constraints placed on u are violated. A suboptimai policy would be to use either u when u* > u , or u - when max max' mm u" < u mm STEP 3, Put 1 + 1, t :d = t (i) +At At and 1 \ v Ct (i:) ) - t (i3 + k x 2 (t (i) ) = t^+k and go to Step 4. m: ;ep is the same as j,n the previous algorithm and is Followed only when x, is internal to the constraints 69 otherwise it is bypassed. STEP 3a. Put i - i+1, and go to Step 6. This step is followed only when any of the constraints placed at x ± are at equality; the value of u* has been determined in Step 2a. The value of A, is maintained constant. STEP 4. Compute z. 1 " s l x STEP 5. Examine the sign of z. If z > + u* = u max lfz<0+u*=u.. — mm If at t^ 1] z > and at t^ z < , set t - t^ These steps are the same as in the previous algorithms and they are bypassed when Xj is either at the upper or at the lower bo un A STEP 6. Determine the current state of the system. ^(j-)'i _ v r+ (i-l)-» . r ,-.('i)^ n L,. S 2 j ~ X ?^ L j T [q?U* 0-s 2 Ci--) + ~ u*]&t c i. V tCl b - xoct"-") * tx^t^h^ct^h 70 This step remains unchanged and it is always followed. STEP 6a. Check the magnitude of x. If x, > a, or x, < put (1) _ ,(i) t - L and (I) ^(t^O = A^t^)^- This step satisfies the jump condition for A, at t^ •* . In addition , X is maintained constant in the interval [t t v j . hquation 4.2.2 3 is used for the computation of CD (i) XjCt^). ?EP 7. Examine the value of H at time t'- 1 -' is h = v ) (x i +x 2 ;)+x i [ci r u]+A 2 [ci 2" 5 2 cl -c 1)+ r 1 ll] = 0? If "yes" ?o to Step 8. it "no" put t : (i) +At a nd return to Step 2a. The Hamiltonian function in this step is computed from Eq. r li r 9 1 4.1.39 since A, is constant in the interval [t v , t K ^ J ] and Eq. 4.1.51 does not apply. STEP 8 Examine the state of the system at t ^ , i Is x, (t^h = and x 2 (t^) = 0? fll and H(t. J ) = 0, return to Step 3 If "no" or H(t^) f 0, put t. t^ , total CD delay = x (t^ J ) , assume new values for k, and k ? and return to Step 2, if "yes" and BCt^} - 0, END. The total delay X ^ • .) and the linai rime equals t v 71 This step is the same as in the previous algorithm. When this algorithm ends, it has satisfied the necessary conditions of the maximum principle, since H is constant and equal to zero. The Hamiltonian function has also been maxi- mized at each time point. The constraints are not violated since u* is determined from Eq. 4.2.32. Furthermore, X. main- tains a constant value during; the period at which the con- stramt is at equality, and the jump condition of section 4.2 is satisfied. When only the second queue is constrained, the algorithm still applies but Steps 2a, 3a and 6a need to be modified as follows . STEP 2 a. Check the magnitude of x 9 , s. 1j -i 1 L If x 2 > a 2 or x ? <_ 0, put u* = [s, (1--) -q, ] — C z J s If U min i U * i U max ^ ut X 2 = a 2 or X 2 = ° and go to Step 3a. Otherwise, the problem is impossib le . STEP 3a. Put i i+1 ■o .(t (iJ ) = and go to Step 6 . STEP 6a. Chech the magnitude o £ X-, 4- K. r i 'i r u J (t (i) ) A 7 (t f or x < put d.u CI 72 If constraints are imposed on both queues and the con- straints are at equality simultaneously, the cycle length must be free to vary. During this, period the. following steps must be followed. STEP 2a. Check the magnitude of x, and x 9 . L, If x, > a, and x n > a n put u* = q, = [s~ (1~— ) -q_ ] — 1—1 2 — 2 r l l 2 - c L 2 J s_ If u mm — ' "max c ~ ~^1 """1 **""' "2 "2 and go to Step 3a. Otherwise the problem Is impossible . If only x, > a, follow the algorithm developed for constraining the first queue. If only x~ > a ? follow the algorithm developed for constraining the second queue. STEP 3a. Put i = i+1 x Ct^D - x 1 Ct (i) 3 = x.Ct^' 1 ^ l i x 2 (t (i} ) - x^ 1 " 1 ^ and go to Step 6. STEP 6a. Check the magnitude of x, and x„ If x 1 '1 put \. (t Uj ) = X, (t 1^ J ' "1 If x ? > a,., put A- (t Ci), f x, > and x- = x 2 ( put c* t(i)l + J ' Vn l-LCq 1 /s 1 )+(.q 2 /s 2 T I f c - < c* < c mi n — the problem Is m ax L possible. Otherwise the problem has no solution. 75 It is possible that during the control period the con- straints are not at equality simultaneously. In this case, the cycle length can be kept, constant for the entire interval [0, t 1 j. 4,5. Some Computational Aspects The computation of the adjoint variables A, (t) and A 7 (t) for the constrained problem requires further development. In section 4.2 it has been shown that \A£) and X n (t) are con- stant when the constraints are at equality, and that as soon as the bounds are reached there is a jump condition that the adjoint variables must satisfy. The constant value of the adjoint variables given by Bqs . 4.2.2 3 and 4.2.29 can be com- puted only If the parameters y and y„ are known. Since the derivation of u, and y. ? is not apparent, it is presented in this section. A closed form solution for u, can be found from Eq. 4.2.23 and Figures 4.6 and 4.7. At time t *• ' it is required that the adjoint variable A, be continuous, i.e., Mt t2 >") - M t(2) + ) (4.5.1) and since A, is constant in the Interval [t^ ■ ', t- 2 - 1 }, it '1 follows that ^(t (1)+ ) X l (t (2) (4.5 Furthermore, Eq. 4,1.48 at times t (2) Uld t ' J y i elds However, from Eq. 4.2.2 3 or, substituting A., (t v -' L -' ) into Eq . 4.5.5 ^-1 int. thus, from Eqs . 4.5.2 and 4.5.6, and, finally, from Eqs. 4.5.3 and 4.5.7 74 , f 2 1 f 2 1 and V tO>) - tCD.i 1 (4.5.3) (4.5.4) A 1 (t (1)+ ) + u 1 "1 1 (4.5.5) V (I), i - t cl} -Vi (4.5.6) Mt (2 b t +k x p 2 (4.5.7) t^ 2j +k 1 = t^+k.-^ (4.5.8) u 1 - t (D„ t (2) < Q '4.5.9) Similarly, y 9 (considering Eqs. 4.1.49 and 4.2.29) Is given b' u ? . t^-t^ < 4.5.10) Thus, the final form of Eqs. 4.2.2 3 and 4.2.29 becomes ) ft^^l A 1 (t x lt t")-) t (D t (2) (4.5.11) an d X 7 (t (3) J + t (4) (4.5.12) 75 Faster convergence and a more accurate solution can be obtained by estimating the parameters k-, and k ? which are required in the first step of the previous algorithms. Since however, k, and k« have no physical meaning, it is difficult to be estimated. Nonetheless, if estimations of r and t 1 are made, k, and k~ can be derived from Eqs . 4.1.50 and 4.1.52 by setting z equal to zero at time x and H equal to zero at time t, . In this manner, a system of two equations with two unknowns, k-, and k ? , is obtained which can be solved for k, and k„. In fact, letting Eq. 4.1.52 equal zero at t = t the following is obtained: s . s (—- - 1) + (k 9 -1 - k ) = (4.5.13) 1 l s l l and from Eq. 4.1.50 at t = t 1 s 2 S 2 L (g l)t x u + (1< 2 — -k x ) - [q 1 + q 2 -s 2 (l--)]t 1 - x 1 - x 2 + k iqi + k 2 [q 2 -s 2 (l-|)] = (4.5.14) The solution of the above system (Eqs. 4.5.13 and 4.5.14) is (4.5.15) ocu+ (a/f ) y - 6 1 , - ( f - 1) t , u "1 ~ VCY/fJ k 2 = (k 1 -a)« (1/f) (4.5.16) a = [ ( s ,, / s -, ) - 1 ] t an d f = s - / s n £ J. £ X Y = q ? -s ? (1-L/c) 5 = qi +q 2 -S 2 (l-L/c) u - u, mxn 1 nu y a t a ~ a t +■ -~ +■ q. ,q» = the flow rates at t = t 7( A final remark is in order before concluding this sec- :ion. From the relationship s - s ? z = (—- -Dt 1 + (k ? -± 1 1 k,3 (4.5.17) and since it was assumed that s, is greater than s,, it JL 6 follows that the first term is always negative. Therefore z changes sign onlv if s s :, — - k, is >0 -> k > k., -± 2 s 1 2 1s (4.5.18) Otherwise, z is always negative and switch point does not exist. When s, is equal to s ? , switch point does not exist since z will always have the sign of the second term. 4,6. The Optimum Cycle Length The cycle length c is a parameter which remains constant throughout the entire peak period. The total intersection delay is a function of the cycle ' length , and the problem is to find the optimal value of c that minimizes the total delay. For practical reasons the cycle length has upper and lower bounds so that c - < c < c . Short cycles create excessive mm — — max lost times which, in turn, cause extreme delays. Long cycles may be ignored by drivers who can possibly think that the s i gn al h as failed. In general, experience indicates that for overs at ur a ted intersections and for single setting of the signal, long cycles result In less delay. This is justified by observing that as the cycle length increases the number of cycles 77 during the peak period decreases and the total lost time de ere ases . In fact, if p is the percentage of' green time G, given to the first approach, then the effective green time is a - pc (4,6.1) where &, is the lost time spent for acceleration and clearance The output rate per unit of time Is given by Y S O" 1°1 c c (4.6.2) The above equation verifies that as the cycle length Increases , the output rate (slope of the cumulative output curve) in- creases since the ratio Z,/c decreases. Similarly, for the second approach the effective green time g ? is g ? = (l-p)c (4.6.3) tli us the output rate [(I" ! S <T ? °? ? can be expressed as %. 2 ^2 (4.6.4) hence y 9 also increases with Increasing c. Therefore, the total output rate (Yi + Y?) io r the intersection increases when c increases. The final time, however, decreases as the total output rate increases and the area between the total input- output curv"es_ (i.e., the total delay) decreases. Thus, it v;d that for single settings of the signal, umizes tin* total delay i.s the maximum has been ostao.1 7S allowable cycle length. The interesting question is whether or not the same principle holds true when the optimal control strategy is to be considered. This question can be answered by using the results of the previously developed theory. In sections 4.1 and 4.2 it has been shown that the optimal con- trol strategy results in less total delay than the single setting strategy. Consequently, the aggregate delay must also decrease with increasing cycle length. The only compli- cation may arise when the cumulative output curves happen to intersect the demand curves before the end of the peak period. In this case, it was shown that the optimal control is to switch at the point of intersection so that no negative queues (therefore, slack time) are allowed. The resulting delay is again lower than that of the single setting strategy, demon- strating that the maximum cycle length minimizes the total delay,. The above results are illustrated by an example in Appendix 1. CHAPTER 5 OPTIMAL CONTROL WITH BUS PRIORITIES 5.1. Statement of the Problem Reduction of bus delays at signalized intersections is one of the major problems associated with bus transportation -\ 22-25 • r • today. Previous studies • have shown that significant delay savings can be obtained by introducing exclusive bus lanes and/or by granting priorities to the buses at signals. The bus priority objective Is of major importance since the bus service cannot fulfill Its function unless bus delays are kept to a minimum level. Furthermore, reduction of bus delays increases the reliability and the level of service of this mass transportation mode, making buses more attractive to new riders. It is evident that bus priorities at oversaturated intersections are even more essential for a successful bus service since the delays at such intersections are substan- tially higher. Clearly, if public transport vehicles are to be given priority at intersections, it must be accepted that this will be accomplished at the expense of the other users of the ■ intersection. That Is, the delays to the private vehicles will in genera]., increase when bus priorities are introduced. In recent rears, however, the Dhilosoohy in traffic managenienc 79 80 has changed and the flow of people is considered to be more important than the flow of vehicles. Thus, when bus priori- ties are to be considered, minimization -of the total passenger delays rather than the total vehicle delays is the objective of the control. Due to the fact that bus volumes are normally fairly low, it is generally true that most acceptable bus priority strate- gies must provide bus priorities on a real-time basis; that is, the expected time of the bus arrivals at the intersection cannot be assumed to be known a priori , and priorities should be given only upon bus detection. In addition, since the intersection is over saturated and long queues are building up during the control period, an exclusive bus lane will be assumed at the bus approach. The bus lane -will not only sub- stantially reduce the bus delays by allowing the bus to bypass the queues, but it will also help to predict the expected time of arrival of a bus at the intersection with reasonable accuracy. In the analysis it will be assumed that the bus demand during the peak period is known and that the buses arrive from the approach associated with the highest satura- tion flow (if the buses arrive from the other approach, similar analysis applies) . With this preliminary Information a control strategy to enhance the bus priority objective will be developed. 81 5.2. Development of the Co ntrol Strategy According to the optimal control policy, during the first interval of the control period [0, x] the green phase is maximum on the bus approach; hence, further extension of the green interval to provide bus priorities will simply violate the minimum green phase constraint on the cross street Therefore, extensions of the main street green phase during this interval are precluded. It is possible, however, to shift the main street red phase to the right or to the left so that upon bus arrival the signal indication is green. This can be accomplished without violating .the minimum green con- straints,. The situation is illustrated in Figure 5.1, in which an""" indicates a bus arrival. When the bus arrives on green no action will be taken by the controller. The new policy provides the same amount oE green time within two cycles on both the main and cross streets and thus the slopes of the cumulative output curves are not affected. During the second interval [x, t, ] the red phase is maximum on the main street; however, it is not possible to shift this phase either to the right or to the left because such control action will violate the minimum green time con- straint placed on. the first approach. Figure 5.2 may be used to clarify this point. An alternative would be to shift the main street green phase to the right or to the left upon bus arrival, as is done with the red phase in the first interval. This control policy, however, '.-.'ill increase the red phase on 82 MinR-s+f—- Max G B^MI -formal cycle Main street p<%> Cross street Main street Shifting to the left IIP * ^%] ■* Min6*J* MinR"*) I1ISL Main street ^mx^m^m [? Cross WL. street Shifting to the right Figure 5 . 1 33 m Max R _^ s _ MinG^ m®m®m XV/yy\ Vy'yVv 77^? ^m^m^ I * I Normal cycle Main street cross street Main S^S8&8£ street MinG Extended cycle Figure 5 . 2 Cross street the first approach (i.e., the approach which is supposed to receive priority) beyond the maximum limit and such a policy is not acceptable since high red phases will disrupt the main street traffic. Another possibility of providing bus priorities during this interval is to extend the green phase (which is minimum) when a bus happens to arrive within a specified maximum range Z after the end of the green period. Since this policy does not violate any phase length constraint it will be adopted here. The policy is illustrated, in Figure 5.2 where an " :: -" Indicates a bus arrival. 84 In summary, during the interval [0, t] the new control strategy will provide maximum green time on the bus approach and, if a bus arrives on red, the red phase will be shifted to the right or to the left. During the interval [t, t, ] minimum green time will be given on the bus approach and extensions will be granted to the buses that arrive within Z seconds after the end of the green phase. In the analysis it will be assumed that the switchover time and the final time remain unchanged. In order for this assumption to hold true it will further be assumed that the bus volumes are low so that the number of cycles disrupted by the buses is relatively small. The objective is to select the optimum value of the maximum extension interval Z that maximizes the total passenger savings resulting from the new policy. The analysis proceeds as follows. Let y represent the number of cycles during the time Interval [x, t-, ] and x the number of buses; the assumption of low bus volumes was meant ■ to imply that x is much smaller than y, i.e., x << y. Thus, the probability of a bus arrival at any cycle is ■• P a - f < 1 _ ■ ■ ■ (5.2.1) where . t - x y = ~~ (5.2.2) Assuming that a bus can arrive with equal probability anywhere within the cycle (i.e.. the bus arrivals within the 86 d = sin D s in A A - 90 + 8 ? ■+ sin A = cos 2 tan 9, Si g - j + s g^ : l°i!iin 2 & max D - o 1 - e ? tan 6 S Cr ' + S cr I 1^1 2^2 1 (5.2.9) (5.2.10) (5.2.11) (5.2.12) (5.2.13) where gl , g\ are given by Eqs . 5.2.6 and 5.2.7, respectively From Figure 5.3 it is also seen that a = (t-, -t) /cos6. (5.2.14) Substituting Eqs. 5.2.14, 5.2.10 and 5.2.12 into Eq. 5.2.9 the following is obtained: VQ 2 d = sinCe, -8,3 37 i -i< cSie-. oose. = Ct r -T)(tane 1 -tane 2 ) ^ [ 5 . Z . 1 5 J and from Eqs. 5.2.8 and 5.2.15 it follows that AD j t , ( t , - t ) ( t an . - 1 an 8 - ) (5.2.16) Equation 5.2.16 is further simplified by using Eqs. 5.2.11 and 5.2.13 to obtain AD c = JT t 1 (t 1 -T)Cs 1 -s 2 ) p. z 2 = az 2 (5.2.17) where a 4c" 9 1 ^ i "^JL^-j-s-j — 1^1 VJ K "l J 2-' v (5.2.18) The maximum delay saved to a bus by extending the green phase in the interval [t, t. ] is equal to the maximum red (1) phase r": * Similarly, the minimum delay saving is r' CD .00 max therefore, the average delay saving is r^i - Z/2 , and the ill cl-A. delay saved to all buses is given by AD B ECr Cl) 4) 1 max 2 J Z rr (l) Z _ r max ' c ■ max 2 c x_ 7 2 2c (5.2.19) If E 1 and E ? represent the average automobile and bus occupancies respectively, then the total passenger savings are ) E 9 - ( a Z ) E - S = AD,, - AD B c fxZ r (1) max X 7 2 2 c - J 1 (E X 2c i', , a E,x r^' 2 max (5.2.20) Th a ie optimum extension is obtained whe n 8 8 dS : d^Z solving for Z r E x + E, a n a. a i z + .J HL^A = o c (5,2.21) (1) E„x r 2 max = Z E ? x + 2E- ca opt From Eq. 5.2.21 the following is obtained (5.2.22) d__y3 dZ 2 = S" E ? x j 2c- + V (5.2.2 3) However, a is always positive because x, E, , E„ are positive, S, is greater than s~ and t-, is greater than x. Therefore, S" I s 2 1° is always negative, indicating that Z (Eq . 5.2.22) maxi- ' & ' ° opt mizes the total passenger savings S (Eq. 5.2.20). A few important: remarks about the bus priority policy are necessary at this point. 1. The red phase during the first interval [0 , t] can be shifted to the right or to the left by at most gJr;. - g T -i niaA mm seconds so that the minimum green time constraint on the bus approach is never violated. 2. The bus priority policy will increase the total green time of the first approach by T (Eq^ 5.2.26) in the interval [t. t J , and because the final time and the switch- over point are assumed constant the maximum green time in the interval [0,T ] will be slightly decreased by the amount 5g TfE Tc (5.2 . 24) Thus the new value of the maximum green time will be 89 a '- J - n L ' - 6 a f" C 9 ? C "i to max °max & ^' A ' •'J This decrease, however, will be very small because of the low b us volumes . 3. The value of the maximum extension cannot exceed an upper limit; this upper limit' fZ ) is equal to e - cAf-' • . . • aax ; L c max °min' extensions beyond this limit will violate the minimum green time constraint placed on the second approach. Thus, if the value of the maximum extension obtained from Eq. 5.2,22 is higher than Z , the value of Z should be used for the Hi 3.X U13.X optimum extension. CHAPTER 6 SYSTEMS OF OVERSATURATED INTERSECTIONS 6,1. F ormulation of the -Unconstrained Problem The problem of optimizing the operation of more than one overs at urate d intersection in succession is studied in this chapter. To simplify the analysis initially two overs aturated intersections, such as the ones in Figure 2.2, are considered. Extension of the theory for more than two intersections is straightforward and is presented in Chapter 7. Consider a system of two intersections serving the traf- fic streams 1, 2, 3, and 4 as shown in Figure 2.2. If it is assumed that (1) the tra\ r el time between the two intersections is zero, (2) no turning movements are involved, and (3) the queue ing storage between the two intersections is zero, the analysis is greatly simplified. However, since the two inter- sections are treated as one, this formulation does not reflect real-world conditions. To place the problem on a more real- istic basis, these assumptions must be removed. The general minimization problem can be formulated in a manner similar to the previous problems, P r o b 1 e m : ' M i n i m i z e t h e del ay f u n c t i o n D = / Cx 1 +x.+x 3 +x 4 )dt (6.1.1) o * 9 91 subject to £ dx 1 = dt dx 1 q 1 -u 1 2 L l, . S 2 2 at l 2 2- c , s -, 1 f, dx 3 dt dx. q 3 -u 2 x dt q, 4 "4 (1-^-3 — u S 3 2 with the boundary conditions x 1 (0) x 2 (0) x 3 (0) x,(0) '1 x. x w x 2 ct 1 ) x 3 Ct 1 ) x 4 (t x ) arid the admissible control domain f 1 1 s., e ■ /c S„g - ' /c 2°min mm - 1 - l 6 max / u„ < s,gj; 3 i/c — 7 & t t1 " "- mm — 2 'max - u = u, (1) max (2) "max (6.1.2) (6.1.3) (6.1.4) (6.1.5) (6.1.6) (6.1.7) (6.1.8) (6.1.9) (6. 1.10) (6.1.11) In the ab o ve f o rraul at i on , t., is the end of the overs at ur at ion period x. (t) = x- is the queue length on approach i, 1=1,2,3,4 q.j (t) = q. is the input flow rate on approach i, 1 = 1,2,: s^ is the saturation flow on approach i, 1=1,2,3,4 u , ( t ) u. [ S ., g, ( t) j /c . Is a control variable associ l s l ated with the first intersectio n u 2 ( t ) = u „ = [s,g 3 (t3]/c 2 i s a c on t r o I v a r i ab 1 e as s o c I a t e d w 1 1 h t h e s e c o n d intersec t i on 92 g. (t) = g. is the effective green time on approach i', 1 x i = 1 , 2 , 3 , 4 fil g„ - is the maximum green time on approach i, 1=1*2 ,3.4 "max rt ' ' ' ' gj" . "l is the minimum green time on approach i, 1=1,2,3,4 c. is the cycle length of intersection j, j = l,2 L. is the total lost time of intersection j, j=l,2 . x. is the queue length at time zero on approach i, 1=1,2,5,4 f x;, is the queue length on the third approach at the final time. The implicit assumption is made here that the cycles c, and c 2 are constant while the green times can take on any value between a maximum and a minimum. At the beginning of the control period the queues may have values other than zero, whereas at the end all queues have been dissolved. The demand on each approach is time varying; however, the demand on the third approach is a function of the output of the first inter- section. This function can be determined by taking into account the left turns, on the first approach, the right turns on the second approach, and the" travel time between the two intersections. Alternately stated, the input to the third approach is equal to a portion of the output of the first intersection after some time delay d-, . If a represents the percentage of through vehicles of the first approach and b the percentage of vehicles turning right on the second approach, then the demand on the third approach is given by 93 q 3 (t) = a 1" " f s 2 [c 1 -g 1 Ct-d 1 )-L 1 ]] I '1 a u 1 (t-d 1 ) + b L S 9 (l-—-j - c l 1 r = a u, (t- d, ) + b I L l 1 '1 u 1 (t 1 -d 1 ) a - b J]u. (t-d ) + bjs 2 Cl~)| S^J X J. ^ i, 1 - 1 (6.1.12) Let and S 2 S 4 s , 1 ' s - 2 1 3 L L ? (6.1.13) (6.1.14) then 6.1.12 can be rewritten as q 3 (t) = (a-b£ 1 )u 1 (t-d 1 ) bm. n (6.1.15) The time delay d, can be assumed to be equal to the travel time corresponding to the average speed between the two intersections. The average speed is either estimated from knowledge of local conditions or, preferably, measured using floating car techniques as suggested in References 26 and 2 7 As in the previous problems, the artificial state vari- able x„ is introduced such that U ax, 3t - VW X 4 (6.1.16) with initial and final conditions Xq(0) = and x n( t i) ree to vary (6.1.17) 94 Considering Eqs . 6.1.13 through 6.1.17, the problem takes the following equivalent form. Problem: Minimize the delay function t 1 Mm D - f (x, +x + x,+x,)dt = x n (t,) - Ma; v 1 2 3 A J ^ 1 J o - -^ (t 1 3 (6.1.18) s ub j e c t to dx f dt dx 1 f. 1 dt dx ? dt dx, 1 2 o 4 ^r u i <VV £ i u i 3 dt ^ dx : 4 = dtT (a-b&, ) U-, (t-d, ) +bm, -u ? (t) q , -m 9 +£ 7 u 4 2 2 2 with the boundary conditions x. (0) = xV and x- ft,) i v - i l ^ 1 and the admissible control domain (j) < ' < u . < u ^ - 1 •* mm — j — max j = 1,2 (6.1.19) (6.1.20) (6.1.21) (6.1.22) (6.1.2 3) i = 1,2,3,4 (6.1.24) (6.1.2S) The implicit assumption is made here that the parameters a, b , an d d 1 are c o n s t a n t . The Hamilton! an function for the above problem is de Fined as 9 5 H = I A.f. = A (x 1 + x 2 + x 3+ x 4 j + A^q^u^ 1 — u + \ (o^-m +1 u ) + ^[(a-bLju- (t-d 1 )+bm 1 -u 9 ] ■ 2 ^t7 •"! -i"! + A 4 [q 4 -m 2 +^ 2 u 2 ] r l v 1" 1 2 (6.1.26) The adjoint variables A n , A-,, A ? , A~, and A, are given by dA, 3H dt 3x Q dX, 3H dt. 3x 1 dA 2 3H dt 3x 2 dA_ 3 3H dt 3x, dA 4 _ 3H = " " x o dt 3x (6,1.27) (6.1.28) (6.1,29) (6.1.30) (6.1. 31) The solutions to the above equations are k n = const -V +k i ~V +k 2 " k t+k 3 - k t+k 4 (6.1.32) (6.1.33) (6.1.34) (6.1.35) (6.1.36) where .,., , k-, , k , k^, and k, are the integration constants U 1 L O 4 Since x n ft 0'- 1 t-. ) is free to vary, it to Hows that dV \ ft ') ^ l± _ = V o l 'i J 8x o rt i J ° (6.1. 37) Hen a 96 A :[ (t) = ■ t + kl x 2 (t) - - t -:- k 2 A 3 (t) = - t + k 3 A„(t) = t + k Sub sti tut.Ing the A ' s Into 6.1.26, (6.1.38) (6.1.39) (6.1.40) (6.1.41) H- -l(x 1 +x 2 +x 3 +x 4 ) + (t+k 1 )Cq 1 -u 1 ) + (t+k 2 )Cq 2 -m 1 +Jl 1 u 1 ) + Ct+k 3 )[Ca-bA 1 )u 1 Ct-d 1 )+bm 1 -u 2 ] + (t+kj [q 4 -m 2 + £ 2 u 2 ] - [-t-k 1 +£ ] (t+k 2 )]u 1 + [(t+k 3 )(a-b£ 1 )]u 1 (t-d 1 ) + [-t-k 3 +£ 2 (t+k 4 )]u 2 - (x 1 +x 2 +x 3 +x 4 ) + (t+k 1 )q 1 (t+k 2 ) (q 2 -k ] _) + (t+k 3 )bm 1 + (t+k 4 ) (q^n^) = z Ll l + C^+k 3 ) (a-bi 1 )u 1 (t-d 1 ) Z-U- + w where *1 7 ^2 w = -t-Wt + k 2 ) -t-k 3 +£ 2 (t+k 4 ) -(x 1+ x 2+ x 3+ x 4 ) + Ct+1 (t+k 4 ) (q 4 -m 2 ) l Jq l (6.1.42) (6.1.4 3) (6.1.44) (6.1.45) This is not a trivial control problem since the control vari- able u, appears in the equations of the process both without delay and with delay d, , The solution proceeds by introducing the shifted Hamiltonian function H, , defined as 97 H- l - I-I(t) + H.Ct+d,) = z 1 (t)u 1 (t) + Ct+k 3 )Ca-bA 1 )u 1 (t-d 1 ) + z 2 (t)u ? (t) + w(t) + z 1 (t+d 1 )u 1 (t+d 1 ) + (t+d 1 +k 3 )Ca-bi 1 )u 1 Ct) + z 2 (t + d 1 )u 2 (t+d 1 ) + w<t+d 1 ) (6.1.46) The maximum principle with nontrivial time delays of the con- trol is discussed in Reference 28, where the necessary con- ditions tor optimality are also derived. Application of the maximum principle to the previous time-delayed system yields the following necessary conditions. Theorem : For the optimality of the controls u, and u and their trajectories, it is necessary that there exists a T nonzero vector function A (t) = U (t), X,(t), \~ (t) , A,.(t) , A^Ct)], satisfying Eqs . 6.1,2 7 through 6.1.31. Furthermore, X (t) is such that dx 3H . . , (6.1.47) (6,1.48) (6.1.49) ar 1 = 9x7 • (6-1.50) dx W = 3AJ . (6.1.51) In addition, the following conditions must be satisfied: dt 3A Q dx 2 3H dt 3 X dx 2 3H dt 3X 2 dx, 3U on 98 1. H(t,u* u|) = Max H(t,u,,u 2 ) ,1*1*1 ff 1 Ct,u|,u*) = Max ^(t.LUj ,u 2 ) t-d 1 <t<_t 1 -d 1 (t>d 1 ) i.e., the optimal control must maximize the Hamiltonian and the shifted Hamiltonian at each time point in the above intervals . 2. H(t 1? uJ,u*) = Condition 2 states that the Hamiltonian function at the final time must be zero. To satisfy the first condition as stated above, it Is necessary to examine the signs of 3H/3u and 3FL/3U as In section 4.1. Thus, differentiating 6.1.42 with respect to U-, , the following is obtained: 3TT7 = z l (6.1.52) and since z, is a linear function of time, there is at most one time point at which 9H/3u, becomes zero. Plotting the function H versus u, , the following results are obtained (see Figures 4.2, 4.3, and 4.4): 1. If |IL - 2 > o * u * - u (1) 3u, 1 1 max 2. If ~- = z. < -> u* = u^ and 3u, 1 - 1 mm l 3. at •*— - = switch from u^ ' to u^.r . 3^2 max mm Similarly, differentiating 6.1.42 with respect to u ? , it can be easily verified that 3 H f?"\ 3u 2 2 max 99 2. ir ?r — ■ = z n < ■* uS = u - and 3u ? 2 2 mm - 3H n e ,4* t, r (2) + (2) 3. at ~ = u switch from u^ J to u v . . 3u 9 max mm Likewise, in order to maximize H, the following control must be applied: 1. If *— = z 1 + (t+d + k„) (a-b£j = z^ > a U-| 1 _L o 1 1 max if v-^ - z o > o ■+ u* = u UJ . 3u ? 2 2 max 3u, — 1 mm 3R 1 m If «-=- = .z, < -»- u* = u lzJ . du„ 2 — 2 mm 3H 1 fV] n 1 fil .5. At — - = z ( - ±J = switch from u UJ to u L1 -\ 3u, max mm 3H i c?i r ?N i At ^ = z - switch from u v " J to u v " J . 3u- 2 max mm It should be noticed that in the common interval [d, , t-,-d, ] both H and H, must be maximized with respect to u, and u ? . Also, since z ? is a linear function of time, there will be at most one time point at which u„ is switched. It is therefore concluded that when no constraints are imposed, the optimal control policies of u, and u ? exhibit at most one switch each n o t n e c e s s a r i 1 y a t the s a me t i me point, In the previous analysis, no specific assumptions have been made concerning the demand curves Q_ , Q ? , Q_, and Q, . Assuming linear demand curves, a closed form solution can be 100 found for the switchover times and the final time t,-. This solution, however, is of little value since linear demand curves are unrealistic. Furthermore, the control policy allows negative queues and it is necessary to develop the theory to remove this defect. 6.2. Optimal Control with S tate Variable Constraints The problem of constraining the queues is discussed in this section. Clearly, the theory developed in section 4.2 is applicable to the queues x-, , x« , and x. since the state equations for these queues are not affected by the time delay d, . However, x 7 is affected by the time delay and it is of interest to examine the case where upper and lower bounds are placed on this queue. If cu and zero are the upper and lower bounds, respectively, it is required that a. (6.2.1) and x, > (6.2.2) When the above constraints are strict inequalities (i.e. , if x^ < a„ or X, > 0) for the entire control interval [0, t, 1 , 3 3' 3 1 the control variables u, and vu are not affected. One only needs to ask how the control is affected when the constraints ( 1 ) f 2 ) are at equality for a finite time interval [t, ' , ti J "\ , 1 3 ' 3 ■ ' i.e., what happens when (6.2.3" 101 or Let and x. = X. a. = (6.2.4) (6.2.5) (6.2.6) Without loss of generality, consider the constraint 6.2.1, Since Eq. 6.2.5 holds as an identity for a finite period of time, i.e., it is true independently of the value of t in the interval [t (1) A2) } , it can be differentiated with respect to time to obtain dx. di dt I . o (6.2.7) or, using Eq. 6.1.22, (a-b&i )u, (t-d, ) + bm. u 9 (t) = hence , u,(t) (a-b^ 1 )u 1 (t-d,) + bm 1 (6.2. 8) (6.2.9) Therefore, when x, is at the upper bound for a finite period of time, the control action at the second intersection at time t is a function of the control action taken at the first intersection at time t-d,. In the special case where a = 1 and 1 , Eq. 6.2,9 yields u 2 (t) = u 1 (t-d 1 ) (6.2.10) Equation 6.2.10 indicates that when no turning movements ar< io; involved, the control action at intersection 2 is the same as the control action taken at intersection 1, d, time units earlier. The adjoint variable X,(t) in the interval [ti , ti ' ] is derived from Eqs. 6.2.9 and 6.2.5. Let R. (a-b£ ] )u, (t-d, ) + bm, = iu (t) = t^<t<t!; 2j (6.2.11) at time w J it is required that V', 15 > - « 3 Ct(«) (6.2.12) :hus . X_ is given by dA dt" - f!£s J-0 1^5 3 u. i 3u„ ' 3R 1 dX. (6.2.15) Substituting R, from Eq. 6.2.11 and the f.'s from the state equations 6.1.19 through 6.1.25 into Eq. 6.2,15, one finally obtains dA dt - t<»<t<t«) (6.2.14) Equation 6.2.14 shows that A~ is constant in the time inter- „ i r*.Cl) ,.(2)1 c „, val [ti , ti -i, Furthermon the following condition (1) , at time tr -' , X, must satisfy JO 3S. - Tj-i - x-(t£ 3 3x, 3 3 (1) p , (6.2.15) Therefore, the constant value of X- during the interval r,(l) ,(2) J is obtained from Eq. 6.2.15. Proceeding as in 103 section -1.5, it can be .easily seen that ,-(D . t (2) < (6.2.16) Since R~ must be zero in the interval [t^ (1) .(2) ti J ] , Eq. 6.2.9 should be used to compute u ? , whereas u, is computed from the signs of 3H, /9U-, and 3H/3u, . From Eq. 6.2.9 it is also seen that s,g t (t) s ? s g , (t-d-,) L ___£_; = ( a -b ~j -i-i i- + bs ? (l---) (6.2.17) Thus, g-(t) is computed from the above relationship. If the cycles c, , c and the saturation flows s 1? s , are equal, it follows that (t) = (a-b i l)g 1 (t-d 1 ) + b ^ (c 1 -L 1 ) (6.2.18) and in the special case where turning movements are pro- hibited , 3 (t) - gl (t- dl ) (6.2.19) i.e., the green time at the third approach is equal to the green time at the first approach d 1 units of time earlier. When constraint 6.2.2 is imposed, Eqs . 6.2.6 and 6.2.7 yield dSL dS. dt dx , dt (6.2.20) Therefore, the same equations apply for the computation of the control variables u and the adjoint variable \~. 104 The problem becomes more complex when two or more con- straints are imposed. For example, suppose that constraints are placed on the queues x ? and x* such that x ? < a ? (6.2.21) and X- < <*- (6.2.22) When constraint 6.2.21 is at equality, u, must satisfy Eq. 4.2.33, i.e., L s U l = [s 2 tl "'c^ :) " q 2 ] s~ (m 1 -q 2 )£ 1 (6.2.23) Similarly, when constraint 6,2.22 is at equality, u,. is com- puted from Eq. 6.2.9. Equations 6.2.2 3 and 6.2.9 form a system of two equations with two unknowns which have the solutions U l = (in l" q 2' £ l (6.2.24) u 2 - (a-b£ x ) [m 1 -q 2 (t-d 1 )3A 1 + bn^ (6.2.25) Therefore, when both constraints are at equality simultane- ously, u. and u ? are uniquely determined from Eqs . 6.2.2 3 and 6.2.24. If, however, more than two constraints are imposed and they are at equality simultaneously, the problem is impossible since it involves the solution of a system of more than two equations with only two unknowns (the two con- trol variables). To circumvent this difficulty, it will be necessary to let the cycles c, or c, or both (depending on the number of constraints) free to vary between a maximum 10! and a minimum value. If the resulting cycles lie outside their specified bounds the constraints will be violated. 6.3. Solution to the Unconstrained Problem For the solution of the general minimization uroblem with time.- varying demands, turning movements, and time delays of the control, it is necessary to turn to numerical tech- niques. If minimization of the total system delay is the only objective of the control, the following algorithm is applicab le . STEP 1. Assume values for k, , k ? , k,, and k A . Since the integration constants k-, , k ? , k-, and k* (Eqs . & . 1 . 32 through 6.1.36) that are necessary for the computation of the adjoint variables are unknown, initial values must be assumed. The optimal solution is found by iterating on k, , k .-, , k,. an d k , . STEP 2. Set t fl} = 0, x^t^) = 0, x^t^ ) = x° , The time is set equal to zero (beginning of the control period) and initial conditions are the ones prescribed for t h e s p e c i fie p r o fa 1 e m . J. £ STEP 3. Put i = i + 1, t^ 1 ' = t^+At and X A ft CDi - t Ci) +lc J — X. r A. ■ 106 >(i), Ai)^ A -^ (^ L "" J — X ■ iv.-j 4 This step perforins numerical integration of the adjoint vari ab les (Eqs . 6,1.27 through 6.1.31). STEP 4, Find the values of z's at t*- 1 -', i.e., z (1} - Z 1 + (a-bA 1 ) [t (l ^ + d 1 +k 3 ] - 8H 1 /3u 1 z x = -t ( '^ - k 2 + ^[t^+k,] - 3H/3u 1 z 2 = -t^ - k 3 + £ 2 [t^+k 4 ] = 3H 1 /3u 2 = 3H/3u. The values of z's are used to determine the optimal policy. STEP 5, Examine the signs of the z's and determine the optimal controls u* and u*. If z^ > and z, > ■* u* = u' ll \ 1 1 max If z^ < and z, < -* u* = u^ . — 1 — 1 mm If Z^ = z 1 ■- - T X - t (i) . If z = >0 ■*■ uS =* u v J . 2 2 max If z < ■> u* - u^ . 2 — 2 mm If Z, = + T 2 - t (1) . The optimal controls u? and u£ must 'maximize the Hamiltonian and the shifted Hamiltonian at each time point in the common interval [d, , t,-d, ]. If m 1 - 1 lies outside of this interval the optimal value of u, is determined only from the sign of F 7 '1 STEP 6. Determine the current state of the system. ^it {l h - H {t il - l h - [ qi rt^^-u lC t^b]At i 107 x 2 (t (l) ) = x 2 Ct (i " 1} ) + [q 2 _Ct Ci) )-m 1 +£ 1 u 1 (t i )]At >w(t (l) ) = x 3 (t (l-1) ) + [(a-b£ 1 )u 1 Ct-d 1 3 + bnu-u, C"t ) ]At x 4 (t (i ^ - x 4 Ct (i - 1} ) + [q 4 (t (i} }-Hi 2 + 2 u 2 (t Ci} )]At x Q (t (l) ) = x (t (i " 1J ) + [x 1 (t (i) ) + x 2 Ct Ci) ) +x 3 Ct Ci) ) + x 4 Ct (:i) )}At, If x i < 1=1,2,3,4 set x. = and follow Steps 2a, 3a, 5a, and 6a of the constrained algorithm. This step performs numerical integration of the state equa- tions 6.1.19 through 6.1.20. STEP 7. Examine the value of H. Is H - z 1 u 1 +(t ( - 1 - ) +k 3 )u 1 (t^ 1 ^-d 1 ) + z 2 u 2 +w = 0? If "yes" put t 1 = t*- 1 -', D= x Q and go to Step 8. If "no' : return to Step 3. Since at the final time H is zero, the process must continue until H becomes zero. The total delay accumulated to this time point and the final time are the optimal if the remain- ing conditions are satisfied. Chech the state of the system at t, . Is the final state reached? If "yes," i.e., if x^t-,) = 1=1,2,5,4 ■* END. If "no" assume new values for x. 1=1,2,3,4 X n n. cl re t u m t o Step 10 8 In this step the state of the system at the final time is checked to determine whether or not the optimal solution has been found. If the final state is the desired one, the assumed values for k, , k~ , k,, k. are correct and the itera- tive process is terminated. Otherwise, new values must be assumed by using an optimization routine which will minimize the objective function I - x^tp 2 + x 2 (t 1 ) 2 + x 3 (t 1 ) 2 + x 4 ( tl ) 2 Therefore, Step 8 Is performed by the optimization routine. The obtained solution is the optimal because when the algorithm terminates, all the necessary conditions have been satisfied. Namely, (1) the Hamilton! an functions have been maximized with respect to time at each time point (Step 5) , (2) H is zero at the final time (Step 7) , and (3) the initial and final conditions are the specified ones (Steps 2 and 8). 6.4. Sol ution to the Constrained Problem If constraints are imposed on the queues, the preceding algorithm applies only when the queues remain below their specified bounds. When the bounds are reached, It is neces- sary to follow additional steps that will be developed in this section. Without loss of generality, it will be assumed that constraints are placed on queue x, which is affected by the time delay d, , i.e. , I x i £ <** (6.1.10 109 To satisfy this constraint the algorithm changes as follows STEP 1. Assume values for k , , k~ , k~, and k,. STEP 2. Set t Cl} = 0, x Q (t Ci) ) = 0, x 1 (t (i) ) « xj , x. It J - X-,, X-^T J - \_ and x,(t v ) = x. Steps 1 and 2 are similar to Steps 1 and 2 of the uncon- strained algorithm. STEP 2a. Check the length of queue x,, If x 3 (t l " LJ ) > a 3 or x„(t Uj ) <_ put u*(t^) - (a-b£ 1 )uj(t (;i ^-d 1 )+bm 1 If, however, u*(t^) < u ^ or u*ft^l > u ^ ' 2 - mm 2 " -> max the problem is impossible. If x 3 (t^) > a 3 or x 3 (t^) < put x ~(t^) = a or X-Ct^J - and go to Step 3a. When the limits tend to be exceeded, the control u$ is com- pute d from Eq . 6.2.9. STEP 3. Put i = i+1, t (i) - t (i) -At and X Q = -1 M't (i) ) = t^ +kl x 2 (t (l) ) = t Ci) +k 2 x,(t Ci) ) = t^+k. A 4 ct j - t 'k 4 Co to Steo 4. This step is similar to Step 3 of the unconstrained algorithm 110 STEP 5a „ Put i = i+ 1 , A (t Cl) ) - -1 x 1 (t Ci:) ) = t (i) +k t'^ + At and -k. A 4 Ct (l) ) = t (i) + k 4 . Go to Step 5a. In this step the adjoint variable X, is kept constant; the step is bypassed if the constraints are not at equality. STEP 4 Find the values of z's at t (i) l . e z^ = z, + (a-b*,)[t^ + d,+k T 3 = 3H./3U, J- 1 13 11 -t^ = k x + ^ [t Cl ^+k 9 ] Z 2 = "* (i.) - k 1 £„[■ ■2 3K/3u 1 Ci)*v k 4 ] = 3H 1 /3u 2 = 311/ 3 u. STEP 5. Examine the signs of the z's and determine the optimal controls u* and u* 1 L If z^ > and z 1 > ■* u* = u^ . 1 1 max If z ^ < and z, < -»■ u* = u^ . 1 — 1 mm f 7 (lj _ 7 _n_ >T _ t (lj I Z Z][ U T 1 Z If Z, -> u* = up\ 2 max If Z 2 < -> u 2 = mm If •7 ~2 = -> T 2 = t<« Go to Step 6. Steps 4 and 5 arc the same as in the unconstrained algorithm. Ill STEP 5a. If z^ > and z, > -* u*- = u^K 1 1 max If z^ Vj < and z., < -> u* = u^\ — 1 — 1 ram u* has been determined in Step 2a. This step is bypassed if the constraints are not at equality. According to the results of section 6.2, uS is a function of u* at time t-cL and is not determined from the sign of z ? but rather from Eq. 6.2.9. STEP 6. Determine the current state of the system. x 1 (t (l) ) = x 1 (t fl_1) ) + [q 1 Ct tl} )-u 1 (t tl ^)3At x 2 (t Ci) ) = x 2 Ct Ci ~ 13 ) + [q 2 Ct (i) )-m 1 +£ 1 u 1 Ct Ci) )]At X 3 (t (i) ) = x 3 (t (i " i:) ) + [Ca-bJl 1 )u 1 Ct-d 1 ) -bm, -v.* C^ 3 ] At x 4 (t (i) ) - x 4 (t (i - 1} ) + [q 4 (t (i) )-m 2+ £ 2 u 2 (t (i) )]At x (t (i) ) - x^t^- 13 ) ♦ [x 1 Ct^ i) ) + x 2 (t^ i b 4-x 3 (t (13 )+x 4 Ct (i) )3At. This step is similar to Step 6 of the unconstrained algorithm, STEP 6a. If x-(t^) < or x 3 (t^) > c* 3 put A.(t W ) = Xjt^ 3 )*]!, and A 1 ^ = t^. This step is required to assure the discontinuity of A~ at time t' 1 '. 5 STEP 7, Examine the value of H. 4 [ s H = I X . f - » ? 1 = x ;i If "yes" put t, = t '■ "■ , D = x Q and go to Step 8. If "no" return to Step 2a. 112 STEP 8. Check the state, of the system at t, . Is the final state reached? If "yes," i.e., if-x-Ct,) = 1 = 1,2,3,4 ■* END.. If "no" assume new values for x. i=l,2,3,4 and return to Steu 2. Steps 7 and 8 are similar to Steps 7 and 8 of the uncon- strained algorithm, with the only difference being that In Step 7 the Hamiltonian function is computed from Eq. 6.1.26. The algorithm satisfies the conditions of section 6.2 since (1] A remains constant during the period at which the constraints are at equality (Step 3a), (2) the jump condition '"1 ) at t^ - is met (Step 6a), and (3) the optimal controls u* and u* in the interval [tj , ti ] are determined according to the procedures developed in section 6,2. When constraints are imposed on the remaining queues, steps similar to 2a, 3a, 5 a , an d 6 a m us t be f o 1 1 ow e d . CHAPTER 7 EXTENSIONS OF THE THEORY 7.1. Single Overs aturated Intersection Thus far, an intersection of two one-way streets was considered. However, the theory can be extended to an inter- section of two two-way streets where more than two approaches are overs aturated (assuming two-phase operation). For example, if the overs aturated approaches are four, the prob- lem is formulated as follows: Problem: Minimize the delay function D = / (x,+x 9 +x, + x,)dt (7.1.1) o S lib j C C t to dx ar" = f i = Q -r u C7.1.2) d X S - dl A - f 2 = V S 2 (1 -c 3 + s7 U C7.1.33 dx, ^ - f- = q,-u (7.1.4) dt ■ j ith the boundary conditions x- (0) - x, (t,) - 1-1,2,3,4 (7.1.6; 113 x CO) - , x (t a ) free to vary 114 (7.1.7) u is an admissible control in the interval (1) s ^1) l^min c = u . < u < u mm — — max S <T 2 "max (7.1.8) The solution proceeds as in section 4.1, I.e., by defining the Hamilton! an function 4 H = E i = (7.1.9) and setting 3H/3u = to find the optimal control. If the final time is fixed, i.e., If the end of the con- trol period is prescribed, it Is evident that the terminal control problem is considered, In this case, the Hamilton! an function at the final time is not zero and the algorithm of section 4.3 .is modified as follows. S T E PS 1 - 6 re m ain un ch an g e d . STEP 7. If t (l] t, go to Step 8, (i) If t l - J < t go to Step 3 STEP 8. Examine the state of the system. Is x 1 (t 1 ) - and x 2 (t 1 ) - 0? If "yes" and H(t^) = H(t,3 END. If "no" or if H(t*- ^ ) f H(t,) assume new values for k, and k„ and return to Step 3, "I "2 If the Initial conditions are different from zero, the only necessary modification would be to sot the values of the stat variables at time zero equal to the specified ones (Step 2). 115 7.2. Systems of Intersections The theory of Chapter 6 can be extended to a system of more than two consecutive overs aturated intersections on an arterial street such as the ones shown in Figure 7.1. To formulate the problem, the following definitions are necessary. M = the number of intersections. d. = -f-i^ the ime delay of intersection i (i = l ,2 , . . . ,M) , i.e., di is the average travel time between intersection i and the upstream intersection. j - the j approach to an intersection, j=l,2. q i j = the demand on approach i,j (i=l ,2 , . . . ,M; 3 = 1,2) i»j) f„(i,i) ls nax " ' ) - the minimum (maximum) green time on appro acn i f j s j_ -j - the saturation flow on approach i,j. U i = s l s i 7 ' c i = the cont rol variable at intersection i i-1,2,. . . ,M. c i = the cycle length at intersection i (i = l ,2 , . . . ,M) . L a- i , 1 the total lost time at intersection i (i=l ,2 , . . . ,M) . = the percentage of through traffic on each hori- :ontal approach i,l (1=1,2 2 - the percentage of vehicles turning right on each vertical approach i,2 (i=l ,2 , . . . ,M) the out 5=1,2). °j a - tae output rate on approach i,j (i-1 ,2 ,. . . ,M; j7\ 2 I 1 r\ n.M/ Fi euro 7 . 1 116 It is noted that q. . is a given function if approach i,j is an external approach such as all the vertical approaches and approach 1,1. If i,j is an internal approach such as all the remaining horizontal approaches, q. . is given by -*- > 3 b-1 'i,j (t) = a i-l,l u i-lO d P * b i-l,2 Si-l.Z^-HT., V 1-1 i " 1 , 2 ,,. , J -s—rT^-l^Vj C7.2.1) Furthermore, the output rate o. -is u i if i,j is a horizontal approach (7.2.2) L. s . _ °i i = s -; ■ O--7— ) - - — '— u. If i j is' a vertical link ,J ~' J i i,l X (7.2.5) The problem formulation Is: Problem: Minimize the delay function t 1 M 2 D = f * ,2 (x )dt (7.2.4) o 1=1 j=l ,J subject to dx. . f i,j = "^ = a i,J-°i,j i-1.2,...,M, (7.2.5) 1 ■*■ ? « with the boundary conditions x i j CO 3 = X° i = l,2,... ,M; j-1,2 (7.2.6) x j iCtO - i=l-,2,... ,M; j=l,2 (7.2.7) and the admissible control domain S.V 1 ' 1 - 5 ,., ... s CT Ci,D J^iIL_ = u CO < Ll . < u d) = S l°max _ c. mm — 1 — max c. J - 1 (7.2.8) 117 The solution proceeds as in Chapter 6, that is, by defining the Harailtonian function as 2 Z i»l j=l and the shifted Hamiltonians M H = I I A . . f . . (7.2.9) H i = H(t) + H(t+d 1 ) + H(t+d. .) i=2,3,.,.,M (7.2.10) The optimal control is obtained by setting dH/3u and 3fT. /3u equal to zero in the appropriate intervals. Constraints can also be imposed on the queues as in section 6.2. CHAPTER 8 CONCLUSIONS AND RECOMMENDATIONS The preceding analyses of the optimal control of over- saturated intersections led to the following conclusions: 1. For a single overs aturated intersection there exists at most one switch point if no con- straints are placed on the queues, 2. When constraints are placed on the queues several switch points may exist. 5. If one constraint is at equality the cycle length remains constant; however, the splits must be free to vary. 4. If two constraints are at equality simul- taneously, the cycle length must be free to vary. ■ 5. In the special case where the demand is such that the intersection operates at capacity during the time interval In which the con- straints are at equality simultaneously, the cycle length is constant. 6. The optimum cycle length is the maximum allow- able cycle length. 7. Bus priorities can be granted without affect- ing the switch point, and the final time. S. For a system of two or more overs aturated intersections, there is at most one switch point per intersection, assuming that no constraints are placed on the queues. 9, If constraints are placed on lengths of queues, conclusions similar to the ones of the single intersection are valid. 10. For a system of two or more consecutive over- saturated intersections , explicit relationships 1 1 S 119 between the control variables exist. That is, if d represents the average travel time between two intersections, the control action at the downstream intersection is a function of the control action taken at the upstream inter- section d time units earlier. Since the work performed in this dissertation is pri- marily theoretical, it presents some hypotheses that require further discussion. The major assumption is that the traffic voium.es during the peak period are predictable. However, the timing of pretimed signals is based on the implicit assumption that the traffic volumes have a repetitive and predictable pactern. Furthermore, case studies" ' have shown that the day-to-day variability in peak period demand is relatively small (approximately 1 percent). Nonetheless, if the day-to- day variability is statistically significant, it can be taken into account by using different timing plans according to the day of the week. Tt is also noted that accurate prediction of the demand is not crucial since the optimal control strateg; results in less total delay than the single setting strategy even if the actual volumes are substantially different than the predicted ones. This is illustrated by an example in Appendix A. The time variation of the demand during the same peak period is significant, but this has been taken into account by assuming nonlinear demand curves. In developing the theory, the implicit assumption was made that the saturation flow is constant during the control period. This, however, is an assumption common in most traf- fic signal control strategies and has been found to be Fairly real is ti c. 120 If real-time (feedback) control is to be considered, the optimal strategy will change frequently, based on information about the current state of the system and the predicted demand for the remaining control period. For this purpose, however, development of an adaptive prediction algorithm will be neces- sary. Some prediction algorithms have been proposed in Refer- ences 2 and 9. Nonetheless, these algorithms have not been used in practice, mainly because they oversimplify real -world conditions. Hence, further research in this area is needed. Improved traffic prediction models will also benefit existing real-time signal control schemes. Extension of the theory to multiphase signals is not simple and should be the subject of future research. The optimal control strategy for multiphase oversaturated signals will certainly become more complex due to the large number of control variables that are introduced. The problems considered in the previous chapters can also be studied with stochastic input. It should be pointed out, however, that stochastic optimal control is a new field in optimal control theory and, due to the complexity of the problems, complete mathematical analysis may not be feasible at tins time, Finally, the travel times (or time delays) between inter- sections were assumed constant. Although this assumption is practically realistic, the optimal signal control, problem with time- varying delays should be considered. At this time, however, optimal control with time- varying delays is a problem 12: that "has not been solved theoretically and further research in this area is needed. APPENDIX A APPLICATIONS OF THE THEORY A . 1 . Introduction So far, the mathematics for achieving the optimal con- trol of overs at ur ate d intersections were developed (Chapters 4-7). Using the results of the preceding theory one can find the optimal control policy for a particular situation. Then the optimal solution can be compared with sub-optimal policies which may require less control effort. Based on engineering considerations and judgment, a decision can be made as to whether or not. the optimal policy should be followed for the particular problem. As in most optimization problems, it is not necessary for the optimal solution to be always highly beneficial when it is compared with suboptimal solutions. It should be remembered that the optimal solution does not always imply bang-bang control; therefore switch points may not exist. For purposes of illustration of the theory, some typical examples are presented in the following sections. For each example a computer program utilizing the appropriate algo- rithms (Chapters 4-7) was developed. The algorithms incor- porate the use of an optimization routine. This routine is based on a searching method to determine the minimum of a function of N independent variables. 123 i In searching, one is interested in finding the set of values of the independent variables which yield the extremum (i.e., maximum or minimum) value for the dependent function. A set of values for the dependent variables is referred to as a location, and hence the general problem can be stated as finding the location at which the function takes on its e xt re mum value . Consider the case in which the initial location is given or selected at random, A new location is to be selected. There are two general qiiestions about the selection of the new location. One is the direction of the new location rela- tive to the old location, and the second is the distance between the locations. There are several searching strategies to resolve these two problems. In the sectioning procedure one moves in a direction which is parallel to one of the coordinates; one independent variable is changed at a time. In the steepest ascent technique one moves in the direction of the gradient of the function. In both of these techniques one can either move for an arbitrarily specified distance or one can move in the same direction as long as the value of the function is increasing (assuming that it is desired to maxi- mize the function). A new direction is then determined at the location of this local maximum. Symbolically, the general search problem can be stated as follows : Max: J - f(X (i + 1) ) - f (X^ + a (i) -p Ci) ) 1 2 4 subject to X v 7 as given p " as determined by a particular method where X^ ; = the i Lj location — (i) *.!. -th j. p v ■* = the i direction a = a scaler indicating distance moved. Once the direction has been chosen, the problem of locat- ing a distance at which a relative maximum occurs is the same problem as searching for the maximum of a function of one variable. In this case the variable is a^ . If one were able to choose the interval of interest and willing to make the assumption that the function was unimodal, then one could 31 use the Fibonacci search technique ' to solve the problem. Of course, there Is no need for determining the location of these restricted maxima very accurately since they may be a long way from the maximum value of the function. In fact, one is forced to make a choice between the time spent searching for the restricted maxima and the time spent in establishing a new direction, A search procedure can be described by stating how the direction vector p is determined. The search methods can be classified by whether they employ knowledge of the first and second derivatives in determining p". Th< re are several interesting points that could be men- tioned about the searching techniques and the interested reader is referred to References 31, 32, and 33 for more details, sln.ce detailed discussion on this subject is beyond the scope of this section. 12 5 The optimization routine incorporated in the computer programs is based on a searching method developed by Powell. Powell has shown that quadratic functions (such as the ones incorporated in the algorithms) result in faster convergence. According to this method, N direction vectors (p.) are set up for a function of N variables. On the first iteration they correspond to the coordinate directions. After N steps, a new direction X T -X„ is added to the set. Then p. is discarded and p. + , is stored in p. (i = l ,2 , . . . ,N) . Thus, the extrapola- tion direction is remembered and incorporated into the search. After N such iterations, all the original direction vectors have been replaced. Evaluation of the derivatives is not necessary and this is one of the reasons justifying the selec- tion of the subroutine. Reference 32 suggests that Powell's method is the most effective for cases where the objective function is a nonexplicit function of the independent vari- ables. The routine (called RMINSQ*) computes the values of N parameters that minimize the sum of squares of M functions. Input to the computer programs are typical traffic param- eters such as maximum and minimum allowable green intervals, saturation flows, cycle lengths, number of lanes for each approach, input volumes per lane in a tabular form, etc, The output of the programs are, in general, switch points (if any), final times, total delays, and all the necessary information that constitutes the optimal control policy. *RM1NSQ is a standard scientific subroutine available at the Northeast Regional Data Center of the State University Sys tern o t Florida A . 2 . ' The Unconstraine d Problem In this problem the objective of the control is to bring the state of the system to the origin in minimum time. Alter- nately stated, assuming that at time t = the queue lengths are zero on both approaches, one wishes to find the optimal control that ends the overs aturation period as soon as pos- sible and minimizes the aggregate delay. The queues are not allowed to become negative during the control period. Consider an intersection for which the following infor- mation is given for the two conflicting streams: Approach 1: Saturation flow: s, = 1400 v P hg = .388 veh/sec N unib e r of 1 an e s : 2 Lost time: 1 = 3 sec/cycle Minimum green time: G> min -' = 50 seconds Input volumes (per lane): 5-minute counts as presented in Table A-l. Approach 2: Saturation flow: s = 1000 vphg - .2 78 veh/sec Numb e r of 1 ane s : 1 Lost time: 1 ? = 3 sec/cycle Minimum green time: G) min ^ = 40 seconds Input volumes: 5-minute counts as presented in T ab 1 e A - 1 . The cycle length is assumed equal to 150 seconds and At equal to 2 seconds. The solution, is given by a computer program which utilizes the algorithm developed in section 4.2. The output of the pro- gram is shown In Table A-2. The first column of the table 127 Table A-l INPUT VOLUMES/LANE £ 5jc it ■=* ^ -* ^ A; ,t .TJC *r £ ^ 3X ;* £ ~ ^ ^c ^ £ ,*; *y ^ * APP«I * APP.2 * TIM" * drj£ * jjs * jSt •£:* iofc x A sn *ifc * % -jt jj! A414. A 5$: Q.» Q» 0» 121 • £6 O 30 . 2CS* 147, 5 » 2 63a 90 Oo 3 i 8 * 2 27 3 1 2 * v 257, 15 3 0* 3 96 a 283, 1300, 430 9 3C7„ 2 1 » 4fc2*, 330* 2400 3 492* 3=2, 2 7 » 523, 373* 3 » 552* 394, 33 00, 5 8 2, 4-1 5 » 3 600a 6 i J , 436. 3 9 0, c4C» 457* 4200* indicates the iterations performed by the program. The second and third columns give the final time and the switch points which are obtained if k, and k~ (the integration con- stants of Eqs. 4.1.48 and 4.1.49) are specified as shown in columns 4 and 5. According to the algorithm, in every itera- tion the new values of k, and k ? are determined by the optimi- zation routine based on the value of the objective function which is shown in column 5. The objective function is equal to the sum of squares of the queue lengths at the final time. The last two columns give the value of the Hamiltonian func- tion H at the final time and the total delays, respectively. Finally, the optimum values of k-, and k ? that minimize the objective function are given by the optimization routine RMINSQ and arc shown below the table. Using these optimum values, one can go back to the table to find the optimal solu- tion. It must be pointed out that the optimal solution is not necessarily given in the last iteration since the 12 8 Table A- 2 IT E P AT IONS tt ■& A -.v jjs x -^ sc ^c ■« % ^ -a; -wr ^c is & ^r jjs ^: $s i; ^ ?L' :.V :a; -x r? ak xc ^ -s -i; ^< ix $z ix ifi, ~>. $t ip -£ ^e^;^ 4cfei< ^:^k^t^:M^^c~jzi: * I * Tl * TAU * Kl * K2 * OBJ a * H * DELAY * * * A ^ **»*st £: jjc -J; i >c -i: te J: £ * ^( ;rc ;& 36 la A ^ -^ ^s « 3k ^ W ^ 5^^ir.a;A :£ 3; _£. ^r *■ jjb $; $; ^ -i )jc -fe li $ •< ^ A 1 1 426» 902a —2569 a 78— 3236 »9 7 96 a 3 0, IS 6 9,1 2 1 426, 3SS, -2568»78-3235»9.7 9 6,8 0,05 69,2 J 1 4 26 a 904, -25 69» 78-3 235a 97 96,8 0,17 69, 1 4 1424. 8S8» -2572,27-3241 -,97 96*9 0, 16 .69,1 5 14 2 8* 9C4, -2567a 28-3231,97 96»7 0,14 69,2 6 1432, 912, -2562429-3221897 96,5 0,16 69, 2 7 1 4 4 i 9 2 8 • -2552,31-3201 a 9.7 96,2 0,19 69 9 3 8 14 56s 9 53 a -2532, 34-31 61 »97 95* 5 0, 11 69,3 9 i 492 j 1 013a - 24 92 . 4 1-3 3 1,9 7 9 4,3 0, 08 70 ,3 10 1438* 10 18a -2 49 So 79-3 86,97 9 4a 5 0, 02 70 9 1 11 .1 4 9 6 * 1018 , -2489«,03-3076,97 94 9 0, IS 70,4 12 1 5 3 • 1020 , -2432 , 23-3 56 ,9.7 93,8 6,73 70,6 13 15 0s "iQ20« -2478a 64-30 61 a 97 93*8 6a 31 70,6 1 4 1500a. 10 20, -2471 « 37-3051 ,97 93,6 5, 46 70,6 1 5 1500* 10 13, -2456a 81-3031 »97 93,7 3,69 70 »6 16 1500, I 016 9 -2431» 34-2995,97 93, 7 0, 66 70 ,6 1 7 1 546* 1 014, -2402*2 4-2956*97 90 a 3 ' 0*01 72 -, 7 13 1 5829 1 012a -2344 e 03-2376,9.7 79.» 8 0, 10 78 »4 19 1672 a 10 10. -234 7a52-2681a97 80,6 0,01 73, I 2 C 169 0s 10 12* -2340» 53-2371 ,9.7 79*2 0,02 78,7 21 1 71 0, 1 C 12a -2333o53-2861,9.7 77«> 6 Oa 02 79,5 22 1 752., 1014, -2319,54-2341,97 74,3 0, 6 31 3 2 3 1 £0 0, 10 16, -2291 9 56-2801,97 70 a 4 0»69 82 a 7 24 1854, 10 16 , -2279), 25-2784,37 65*7 0, 03 84*5 25 I 8 2 a 1 23, -2234a 25-2786,95 6 8a 9 0., 3 83 3 C 2 6 16 8 8 « 1006, -2274, 25-2781,78 6 2a 6 Oa 04 85 , 9 2 7 1 97 9 9 3 2 3 -2264* 2 5-2776 » 61 5 5*2 0,01 89, 1 p « 2 23 8a 9 38 s -224 4,2 5-27 6 6,28 32 ,5 a 5. 9 7 , 1 2 9 15002* £ 5 , -2204,, 25-2745,60 1 3 a 7 - 1 1 a C 1 07»9 3 2 72s 960., -2 2 54, 18-27 71a 41 46a 1 0,01 92 a 7 3 1 2 1 56, 9 3 8 a -2247, 66-277.U 23 38,9 , 1 95 a 6 3? 2 3 4 4s 9 40. .» - 22 40 „ 84- 2 7 6 1 « 2 3 22,4 0, 00 98,9 3 "3 2 700« 940 „ -2234«C2~2 75ia28 13,3 2,23 101,2 3 4 2656s 940» -2236., 52-2754, 94 1 4 .» 7 0,0 I 1 « 1 3 5 23 3 2* 9 4 8 , -2241 a 52-2753*72 2 3,1 0, 9 3, 4 3 6 2 7 0a 93 2 « -2231 3 52-2 7 51 „1 6 18,9 la 89 101,7 37 26 86»> 9 3 8., -2235-, 53-2754,20 17,2 0, 01 101,3 3 3 2622, 9 4 2 , -2 2 37 a 7 2-27 55 a 8 5 12, 1 a 100.9 3 9 2 613, 942, -2238*01-2756,07 11,9 0,01 100,9 40 26 26 • 9 56 a -2238, 17-2751 ,07 11,0 0,01 10 0, 1 41 2 644 s 968 9 -223853 4-2746*07 11,3 Gt»01 99,4 42 2 6 3 4 * 558, -2238a 21-2749,87 11,4 o, ci 100,, 4 3 2624, 952* -2238*13-2752*47 11.3 0,01 100,3 A '■+ 2 £ 3 9 , 5 t4 9 -2 23 8* 17-2751 ,31 1 1 a 6 0*01 100, 2 45 2 6 3 4s 9 56a -2233, 19-2750*55 1 1 a 6 0,01 100,1 4-6 2d93» 974, -2240, 13-2746,07 7,4 0, 00 93,9 i? 2 5 6 2 * 994=, -2242 a 03-2741*07 3,5 0, 01 97,8 4 8 2314a 10 13a -22 44. a 4 3-2 7 35. s 6 24, 1 0, 00 94,9 4 9 2 5 7 6 » 986, -224 1 .,23-2 743,12 4,9 0,01 96,2 5 2 5 6 2 o 9 9 2 o -2 241 a 77-2741 ,36 3, 7 » 1 9 7 ., 9 5 1 2 6 * 9 74 a -2 2 39 a 98- 2 7 46 * 7 7,5 0,01 9 9 , 9 52 2 32 6., 1 1 4 , -2244, 1 9-2736, 07 22,9 a 95,2 b 3 2 5 76s 9 86 , -2241 „ 2 0-2743 8 I 7 4 * 9 0. 01 9 3,2 £ 4 2572, 9 9 a -2241 „ 72-2 741 ,9.4 4 ,> 2 98,0 5 3 si D U *$ 3. 9 9 4 ^ -2241,, 98-2 741» 32 3 4- 0,00 97,3 $ --■ V -. >& £ v -ir ;i)S -£ ^ i< 4; ~ *i -,? X :U ,)t ,-=c 5JC SjC ^fi .-^ & ^ J ,t A ^ rX £e .Jfi "*. & Se$ -A; jfc ->; i< Sjc jW if ^ ^C -i- -;; £< 'a --. -.^ ^. _» m ^ ^i. _^ ^ LiPTIMAL SGUUTICN IS FOUNO,FO« ■' t = - Z 2. 4 1 , 9 7 7 K 2 = - 2 7 4 1,318 FIXED C DELAYS- 123 a 3 optimization routine performs various tests to ensure as much as possible that the global minimum has been reached. From the computer printout (Table A-2, bottom) it is seen that the optimum values of k. and k. are -2 241.9 8 and -2741.32, respectively; from Table A-2 one can verify that these values are obtained after 55 iterations. On the 55th iteration it is observed that the switchover time is 994 seconds and the final time 2558 seconds; thus the optimal control policy is to give maximum green time to the first approach (therefore minimum green time to the second approach) from the beginning of the oversaturation period until time T = 994 seconds; after this time minimum green should be given to the first approach and maximum to the second. The total delays that result from this strategy are 97.8 vehicle hours. However, one may choose not to follow the optimal policy and impose the single setting strategy. The single setting that ends the oversaturation period at time 2558 can be computed from the slopes of the output curves as follows: u l = slo ? e of output curve of approach 1 = constant a . to tal output i n time 2 55 8 4 7 7* 2 55 8 2T58" 0.1865 and since 3 l g l "1 c follows that *Froin Table A-l 130 (0.186 5) -150 . 5 8 S 72 seconds or G, = 72 sec + 3 sec ( = lost time) =' 75 sec = 0.50*c therefore, G ? = (l-O.SO)-c = 0.50-c. The total delay can be computed in a manner similar to the bang-bang control (i.e., the area between the input-output curves). The total delay- resulting from the single setting strategy is also shown below Table A-2 and is equal to 123.3 vehicle hours. Thus, the delay saved to the drivers is 123.3 - 97.8 = 25.3 vehicle hours. This means that the average delay per vehicle is reduced by the amount 25. 2(477) + 341 71.0 second; It is therefore concluded that the bang-bang control is highly bene ficial . A. 3. The Optimal Cycle Length The problem of finding the optimal cycle length was dis- cussed in section 4.6, where it was concluded that the opti- mum cycle length is the maximum allowable cycle length, a pro^ ce dure already used in practice. In this section a numerical example is given to demon- strate this point. The input volumes, the saturation flows, and the remaining traffic parameters are the same as in the previous example. In addition, the upper and lower bounds ■placed on the cycle lencth are assumed to be 100 and 1000 131 seconds , respectively. A cycle length o£ 1000 seconds is, of course, too high to be practical but is used here only for illustrative purposes. The total delay, the switchover time and the final time were computed for cycle lengths of 100, 200, . .., 1000 seconds and the results are illustrated in Figures A. 1 and A. 2 . The effect of the cycle length on the total delay is shown in Figure A.l. As can be seen from this figure, the total delay falls sharply when the cycle length is between 10 and 30 seconds. For cycle lengths greater than 300 seconds, the delay savings are relatively small. Figure A. 2 shows the effect of cycle length on final time and switchover time. The dashed line in this figure shows the effect of cycle length on final time, whereas the solid line shows the effect on switchover time. Final time decreases with increasing cycle length, as expected. Cycle length also affects switchover time because of the change of the maximum output rates on each approach. That is, the maximum output rates (as defined in section 4.1) increase with increasing cycle length. In Chapter 4 it 'was shown that the switchover time is either the time x at which the z function (defined also in section 4.1) becomes zero or the time t^" J at which the maximum cumulative output curve of the first approach intersects the demand curve. If x is greater than t - - the switchover time is t^^ J , so that no negative queues are allowed. The intersection of these two switchover time functions produces the peak at c = 200 in is: no 100 - (/) 90 - S 80 * 70 60 5 2600- u o to 6 £ 2500 rH aS ■H 2400 100 200 300 400 500 600 700 800 900 1000 Cycle (sec) Figure A.l 10 2 00 ~ r~ 1 r~~ 400 500 600 Cy c 1 e ( sec" Figure A. 2 900 u soo e o -700.5 600 y •H - 5 00 i 1 r r '00 800 900 1000 135 Figure A. 2. When c equals 100 seconds, x Is less than t ^ , i.e., the switchover point lies below the cumulative demand curve. When c is greater than or equal to 200 seconds, t is greater than t^^ J and the switchover point is the point of intersection of the input- output curves. A . 4 . T he Fixed Final Time Problem In this problem it is assumed that the final time is not free to vary but it is fixed. The objective of the control is to bring the state of the system as close as possible to the origin (zero state) at a given time t-, . Suppose that in the example of section 4.2 the final time t, is equal to 2100 seconds. The question arises then as to how the control is affected by this objective. Alternately stated, it Is of interest to know if a switch point still exists, and If it is the same as in the free final time problem. The appropriate algorithm for the solution of this problem, as given in sec- tion 7.1, is incorporated in a computer program that generated the output of Table A- 3.. Inputs to the program are the same as in the previous example, the only difference being that t, is equal to 2100 seconds. The output of the program is Interpreted in a simi- lar manner as before. It must be pointed out that since the final time is net free, the Hamilton! an function does not have to be zero. The optimal solution Is obtained in the 14th iteration for k = -260 3.78 and k, - -3256.82. The new switchover time is 9 70 seconds and the total delays 134 Table A- 3 T £ r. A T I C N S « I * Tl * TAU * Ki * K2 * QQJ* * H * DELAY * :*Ji«A*aa-ti*-Siis*x^3aiA*i?--i*a:^ ■$: * ,ft ■% 3? if if <8 -Jf * 4> ^ *• ** 5ft* 5K ♦ ♦ w ^ * * ^ * * ♦ ~ 1 2100, 502* -2569»78-3236»97 44,33 49,17 S5<,8 2 2100, 893» -2568.78-3236,97 44 a 42 49302 2 2X00* 9C4, -2569* 78-3235*97 44,29 49,15 4 2100, 333* -2572.25-3241,97 44„42 49* 57 5 2'iGO, 9G4* -2567. 27-3231*97 44,29 43,72 o 21C^ 9C6* -2365.2 2-3 229*39 44*25 4 8,56 7 210 3* Si 4, -2 551 * 20- 32 19., 39 44*10 4-7,7 7 a 2100* 924, -2553*74-32 35,0 2 43«94 46*53 9 2100* 940=, -2543.70-3165902 43,75 44,94 10 2100 3 938 4 -2539*51-3180.02 43,77 44*32 13. 2100* 942, -2547^88-3 190*02 43,73 45=57 12 2100, 946a -2556., 25-3200*02 435.70 46*82 13 2100s 954-, ~2572 i 93-3220.,02 43,65 49,33 14 2103=, 970* -2603*73-3256.32 43,61 53*99 15 . 2100* 970a -2607,37-3261*32 43*61 54,54 1c 2100., 970, -2614 3 56-3271 ,8 2 43*61 55*64 17 2100* 970, -2623*93-3291,82 43*61 57,83 18 2100* 972=, -2657*66-3331*32 43*61 62*29 19 2100* 970, -2549»90-3181»82 43*61 45*74 20 2100a 970* -2576, 84-3219*32 43,61 49,87 ■■* CPTIMAL SOLUTION IS FOUNCFCq Kl = -2603,73lK2=-3256«iS23 95 * 9 95s 7 95 a 9 95* 7 95 » 6 95» ~5 94, 9 94, 2 94. 3 94, 1 94* 93a 7 93, 95 » 93, Q 93, 93* 93, 93, accumulated until t-, = 210 seconds are 9 3,0 vehicle hours. Therefore, it is concluded that the switchover time with fixed final time is, in general, different than the switch- over time corresponding to the free final time problem. A. 5 . Th e Constrained Problem The optimal solution of section A. 2 minimizes the aggrs gate delay subject to lower bound constraints, but it does nor take into account the maximum queues that develop on the two approaches. In fact, if the demand curves have the general shape of Figure A. 3, the bang-bang control results in lower maximum queue length on approach 1 and higher on 13S Q] n Figure A. 3 approach 2 than the single setting control. This can be visualized by inspection of the figure. The output curve OAB results in lower queues on approach 1 than does the output curve OB, Conversely, on approach 2 the output curve OA'B' results in higher queues than does the output curve OB'. Thus, in general, it is the second approach that suffers if no constraints are placed on the queues. 136 Using the results of section A. 2, one can easily verify (by plotting the input-output curves or by numerical integra- tion) that the maximum queue length on approach 2 with single setting is approximately 80 vehicles. If the bang-bang con- trol is imposed the maximum queue on the same approach occurs at time x = 994 and it is equal to X 2 = Q 2 (t) - G ? (x) = 204 - {[(0.35)150-3] (0.278)/150) • 994 = 204 - 91 = 113 vehicles Hence, the maximum queue on this approach increases substan- tially with the bang-bang control, and it is desirable to impose constraints. In this example it is assumed that the second queue is constrained so that it does not exceed the limit of 80 vehicles. The results (following the theory and. the algorithm of sections 4,2 and 4.4) are summarized in Table A. 4. The optimal solution is obtained on the 21st iteration for k., = -2361.48 and k ? = -2651.99. The optimal control strategy is as follows: 1. From t = to t = 47 8 , u* = u ' max 2. At t = 4 78 (switch 1) the queue on the second approach is 80 vehicles and u* takes the value Of 0.191. 3. At t = 15 2 (switch 2) the queue on the second approach is less than SO vehicles and at this time u" becomes maximum again. 4. The average value of u* in the interval [478, 1502] is .191. 5. At t = 16 36;, u* is switched From maximum to minimum. 137 Table A- 4 1 i c .-■ -j -a -J? -i -•, >■ A ji -fc i * * ■* * ■» ~ • * £ $ jje ^s * * ^ * *at * jt rx >■: A 5S« ."=; at A :js .)js * A * iri? ^^ ^: s« ^ :X ^^(^ixSi* * I » Tl * TAU # Kl * ., K2 - 03J» * H * DELAY * » jit £ * Jj & :h. -if -^ rx i;ij*rii**^**?*^**)i:»?3*j* *;*,»:*--**:= it tt & 3- ;ar ^k la; ii?5c^-<Siic^:5c#c^; 1 1 680, 16 2™ -24 74., 65-23 24 9 1 2 80 « 5 • 3 83, 5 2 .16 30, 1 602* -2474* 65-2324 £ ,l 2 80*5 0.03 84,2 3 163 0» 1602 9 -24 74 «, 6 5-2324*1.2 80,5 0, 03 84 a 2 4 1634, 1558, -2473.65-2824.1 2 80 „ 1 * 1 34,4 £ 1 5 3 a 1604, -24 74, fc 5- 2 3 23,1 2 80 9 6 0,01 84,2 5 I 6 3 o * 1 6 C 6 a — 2 4 7 2 o 2 8— 2 3 I 5 » 1 2 S ,> 1 » 1 84* 4 7 2 694* 1610 9 -2469. 92-2314 ,1 2 79*6 G a 10 84. 7 a 1 706a 1618* -2465s 20-23 04.-, 1 2 73 • 9 0, 04 85 a 1 9 1722* 1 6 23 » -2459,53-2792*1 1 77 » 9 0, 04 85 a 7 1 17 50 9 1645-, -2450a 09-2772^1 1 76 »1 0,0 3 66 a 6 1 i I 8 9 16 80- 3 -2431 •20-2732«l 1 73, 2 2s 2 2 83,1 12 1 3 C • 1 676 * -2426.90-2727*1 1 7.3 »0 Is 57 83 a 1 1 3 laoos 1674 a -2422=, 60-2722*1 1 73,0 0* 99 88,1 14 13 0a 1672* -2420.3 5 8- 2719. ,77 72=9 Os 63 83, 1 1 5 1 822* 16 68.5 -2411 a 99-2709*77 7 0,9 0*02 83. 9 3 16 19 4 0., 1553* -2394, 79-2689 s 77 60 « 3 0, 02 92 <> 3 17 2626 3 1638, -2360,40-26 49 ., 7 7 8»3 0, 00 10 0,9 13 2458a 1634, -2362a 84-2654*77 9.5 100,3 3. 9 2700a 1642 , -2357, 95-2644»77 14» 7 1,41 100 a 3 2 2573, le35» -2361 * 31-2651 ,64 5, ,3 Q.00 100 ,9 2 1 2 S 6 6 a 16 36, -2361s 48- 2651 „ 99 5»7 0» 00 1 » 9 2 2 2664 5 1634, -2359 » 12-2649*59 12,9 0*00 1 G 1 „ 2 3 23 94 a 16 38, -23 63a 84-26 54*3 9 13*2 0,00 100,3 2 4 2 5 fc3 6 , 1 6 36 » ~2361»04-265i»54 6 » 100 .9 2 5 2 5 7 2 , 1 6 3 6 ■> - 2 3 6 1 , 3 5-2 5 51*35 5,7 v , j j 1CQ»9 !«ii a * -j 7 ';.• * A :'x :■: -^ *S fc ^ ' . ys £ x if, -,'", -v r, ; - -x. -x is .,< is- M "- -■;* it y. to -;< A A ;< sV >■ ** **i» *■* if. it A -.-; lit A 4s $ * r OPTIMAL SOLUTION IS FOUND* FOR Kl ~~2 3 61* 481 K2=- 2651,93 3 a ITCH I = 478, LCCNSTR. =0al91 SWITCH 2 = 150 2., The trajectory of u is illustrated in Figure A, 4. The total delay with this control is 100,9 vehicle hours, which is still substantially less than the single setting control From this example it is seen that the control effort in- creases as the performance requirements increase, as expect* i ' u u mar .191- mm ' 478 ISO 2 16 36 Figure A. 4 2561 A . 6 . Se n s itivity An aly s is The demand volumes are input parameters that are assumed to he known for a particular intersection. In the timing of pretimed signals is based on the implicit assumption that traffic volumes are repetitive and predictable. The pre- dictability of traffic is generally recognized as a fact, and 29 30 previous studies ' have shown that hourly volume variations for urban streets are fairly consistent. As an example, a report on the traffic, counting program in Cincinnati ' showed a variation of less than 1 percent during the peak periods -within a year. The total delay (objective function) changes if the demand volumes (input parameters ) are other than the predicted ones; however, the control action will remain the same when the signal operates on the pretimed node (open loop control). the one that corresponds. 139 to the estimated demand volumes. Based on actual counts, one can determine the daily variation of the demand volumes and study the effect on the total delays. Although the day- to-day variability is expected to be small, the variability within the peak period is significant;"" ' however, it has been taken into account by assuming nonlinear demand curves. This is indeed one of the advantages of the previously developed th e o r y . It will now be assumed that the volumes at the inter- section considered in section A. 2 can either increase or decrease by at most 10 percent. The total delay resulting from the two types of control (single or double setting) and the three volume conditions are calculated and summarized in Table A-5. The delay units are in vehicle hours. Table A-5 ^\Volumes St rat e gy^-v. -10% Predicted + 10% Single setting Doub le setting 74.1 5 7.0 12 3.3 9 7.8 19 3.1 175.9 From the tabic it is seen that when the volumes increase by 10 percent the total delay corresponding to the double sotting strategy increases by nearly 80 percent, whereas the delay with single setting increases only by 56 percent. The 140 double setting strategy, however, still results in lower total delay than does the single setting strategy. When the volumes decrease by 10 percent, the total delay corresponding to the double setting strategy decreases by 42 percent while the decrease with the single setting strategy is 40 percent. Again, the double setting strategy results in less total de 1 ay . The results are illustrated in Figure A. 5 in which the total delay is plotted as a function of the volumes and the two control strategies. Clearly, the two curves do not cross over, Hence, it is concluded that the optimal control strat- egy results in less total delay than does the single setting strategy even in the case where the actual volumes are sub- stantially different than the estimated ones. This conclusion is important since it suggests that the developed theory is applicable in situations where accurate prediction of the demand is not possible. 200- 1S0-L (3* 10 2 so- — — . Single setting Double setting 10% + 101 Volumes Fi euro A. 5 LIST OF REFERENCES 1. D.C. Gazis and R.B. Potts, "The Overs aturated Intersec- t i oil , ' ' Proceedings of the Second International Symposium on the Theory of Road Traffic Flow , J. Almond, ed. , Paris: Organisation for Economic Co-operation and Devel- opment, 1965. 2. A.J. Miller, "A Computer Control System for Traffic Net- works ," Proceedings of the S econd International Symposium on the Theory of Road T raffic Flow, J. Almond, ed. , Paris: Organisation for Economic Co-operation and Devel- opment, 1965. 3. A.J. Miller, "Computers in the Analysis and Control of Traffic," Traffic Quarterly, Vol. 19, No. 4, 1965. D, Ross, R.. Sandys and T. Schlaeffi, "A Computer Control Scheme for Critical Intersection Control in an Urban N e tw o rk , " T r an s p o rtation Scienc e , Vo 1 . 5 , N o . 19 7: D. Longley, "A Control Strategy for a Congested Computer Controlled Traffic Network," Transportation Research . Vol. 2, 1968, B. Lee, K. Crowley and L. Pignataro, "Better Utilization of Signals Under Oversaturated Flows," Highway Research Board, paoer presented at the mid-year meeting, Summer, 19 74 (unpublished). D.H. Green, "Control of Oversaturated Intersections," Operations Research Quarterly , Vol. IS, No. 2, 196 8. . C! . Gazis, "Optimum Control of a System of Oversaturated Intersections , " n Derations Research, Vol. 12, No. 6 1 Q 6 s M.I. Weinberg, H. Goldstein, T.J. McDade and R.H. Whalen, "Digital Computer Control System for Traffic Networks," NCHRP No. 29-, Highway Research Board, Washington, D.C, 1966. 10. D.C. Gazis, pp. 204-205 raffle Science, New York: John Wiley, 1974, 141 142 11. H. Kwakernaak , "On-line Optimization of Stochastic Con- trol Systems," Proceedings Third International Congress of International Federat i on of Automatic Control , London: Organisation for Economic Co-operation and Development, 1966. 12. L. Pignataro, K. Crowley and B. Lee, "Traffic Control in Oversaturated Street Networks ," NCHRP Project 3- (18) , Highway Research Board, Washington, D.C., 1974. 13. P.G. Pak Poy, "The Use and the Limitation of the Poisson Distribution in Road Traffic," Proceedings Second Confer - ence of Australian Research Board, Australian Research Bo a rd , Sydney , KusTraTx3r^~T^62~r~ 1 4 . A dvanced Control Technology in Urban Traffic Control Systems , Vol. 1, New York: Sperry Systems Management Division, 1965, 15. R.L. Gordon, "A Technique for Control of Traffic at Critical Intersections," Transporta tion Science , Vol. 4, No. 3, 1969. 16. L.S. Pontryagin , V.A. Boltyanski , R.V. GamkreLidze and E . F . M i s h ch e nk o , The Mathematical The or y of Opt imal Processes , New York: John Wiley, 1962. 17. M. Athans and R.L. Falb , Opti mal Contr ol, Mew York: , McGraw-Hill, 1966. 18. M.M. Denn, Optimization by Variational Methods , New York: McGraw-Hill, 1966. 19. L.B. Coppel, Intro duction to Control T heory , Engelwood Cliffs, New Jersey: Prentice Hall, 1968. 20. F.V. Webster, "Traffic Signal Settings ," Road Research Laboratory, Paper No. 39, Her Majesty's Stationery Office, London', England, 1958. 21. J.M. Powell, "An Efficient Method for Finding the Mini- mum of a Function of Several Functions Without Calcu- lating the Derivatives," Compute r Journal, Vol. 7, No. 2, 1964.' 22. H.K. Evans and G.W. Skiles , "Improving Public Transit Through Bus .Preemption of Traffic Signals," Traffic Quarterly, Vol. 24, No. 4, London, England, 19 70. ■.Junction Priority for Public Transport, ,ab oratory, Report L.R. 5 70, London, R.A. Vincent , i*.o a ci Research Eng 1 s md, 19 7 3 143 24. "A Bus Priority System for Traffic Signals," Joint project between Kent State University Campus Bus Service, the' Center of Urban and Regional Studies, and the City of Kent, Ohio, prepared for UMTA (Project Ohio MTD-4) . 25. H.S. Levinson, W.F. Hoey , D.B. Sanders and F.H. Wynn , "Bus Use of Highways: State of the Art," NCHRP Report 143, Highway Research Board, Washington, D.C., 1973. 26. D.T. Robertson, "TRANSYT: A Traffic Network Study Tool," Road Research Laboratory, Report L.R. 65, London, England, 1965. 27. R.A. Vincent, "Traffic Survey Equipment for Measuring Journal Time," Road Research Laboratory, Report L.R. 65, London, England, 1965. 28. A. Wierzbicki, "Maximum Principle for Processes with Non-trivial Delay of the Control," Automation and Remote Control , Vol. 10, 19 70. 29. Highway Capacity Manual , Special Report 37, Highway Research Board, Washington, D.C., 1965. 30. D.R. Howie and J.K. Young, "The Traffic Counting Program in Cincinnati," Proceedings Highway Research Board 1957, Highway Research Board, Washington, D.C., 1957. 31. D.A. Pierre, Optimization Theory with Applications , New York: John Wiley, 1969. 32. M. Auriel and D. Wilde, Optimization and Design , Engel- wood Cliffs, New Jersey: Prentice Hall, 19 73. 33. D.J. Wilde and C.S. Beightler, Foundations of Optimiza - tion, Engelwood Cliffs, New Jersey: Prentice Hall, 1967. BIOGRAPHICAL SKETCH Panayotis George Michalopoulos was born on June 7, 194 8, in Nafpactos, Greece. He attended public schools in Greece and was graduated from El High School of Thessaloniki , Greece, in. June , 196 5 . In September, 1965, he enrolled at the Higher College of Engineering of Athens and received the Bachelor of Science degree in civil engineering in October, 1969. From October, 1969, to June, 19 70, he was employed as a highway engineer by A. Loukakos and Associates, a consulting firm in Athens, Greece. • He entered the Graduate School at the University of Florida in September, 1970, and was awarded a Graduate Research Assistantship in the Department of Civil Engineering. He received the Master of Science degree with a major in trans- portation engineering in March, 19 72. From March, 1972, to September, 1972, he was employed as a traffic engineer by the Florida Department of Transpor- tation in Fort Lauderdale, Florida. In September, 19 72, he enrolled in the Graduate School at the University o£ Florida and began work toward the Doctor of Philosophy degree wi th a major in transportation engineer- ing. He lias held a Graduate Assistantship with the Department of Civil Engineering. 14 4 I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. A,? J ./ k:j Wat t lewo r th , Chairman Pipfessor of Civil Engineering I certify that I have read this study and that in ray opinion it conforms to acceptable standards of scholarly resent ation and is fully adequate, in scope and quality, P as a dissertation for the degree of Doctor of Philosophy. . , y y ■y' yy K..--G. Courage Assistant Professor of Civil Engineering op: I ce ri .nion it fy that 1 have read this study and that in my :onforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. £^£€^£ f* M& "- 1H . S ch aub rofessor of Civil Engineering I ce r -j- 1 fy th pi XI i on i t c on f o r p 'fCs s entati on and a C cl di s s e rt ation at I have read this study and that in my ms to acceptable standards of scholarly is fully adequate, in scope and quality, for the degree of Doctor of Philosophy. t // y< //' / i/ V. S: " D" Assistant Pr Civi 5 s o r of certify that I have read this study and that in my it conforms to acceptable standards of scholarly ■presentation and is fully adequate, in scope and quality, as a dissertation fo: the degree of Doctor of Philosophy. ,/ <? R, ST T e avenwort h Professor of Industrial and Systems Engineering I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and Is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. // ,/-"""" err, i (.,,/ ^vr^z v.^ L?'p J 1 & y. G. Stephanopoulos Assistant Professor of Chemical Engineering, University of Minnesota at ion w P P-r inis disse the College o w a s a c c e p t e d as p the degree of Doctor submitted to the Graduate faculty of and' to the Graduate Council, and artial fulfillment of the requirerac of Philosophy. nts ecember 1 Q 7 C Dean , Colleges, of Engineering Dean , idu a.re School